有向无环图遍历...需要帮忙吗？

Question

我在这里有点力不从心，需要请教朋友。我有一个需要遍历的有向无环图，而我第一次接触到图论时遇到了困难。最近我一直在阅读相关资料，但很遗憾我没有时间去学习它。有人能帮我一下，告诉我如何处理这个树吗？

以下是规则：

- 有n个根节点（我称之为“源”） - 有n个终端节点 - 源节点带有数字值 - 下游节点（我称之为“工作”节点）对传入的值执行各种操作，如加法、乘法等。

如您从下面的图中所见，节点a、b和c需要在d、e或f之前被处理。

正确的遍历顺序是什么？

- Scott

Answer 1

我会研究有向无环图的线性化，这可以通过拓扑排序来实现。

据我所记，线性化基本上按一定顺序排序，保持所有节点（Node_X）对于任何其他给定节点NodeA的出度，NodeX都出现在NodeA之前的不变性。

这意味着，根据你的示例，节点a、b和d将首先被处理。第二个是节点c。最后是节点e和f。

http://en.wikipedia.org/wiki/Topological_sorting

- Nadir Muzaffar

---

我目前正在为图表中的每个条目存储一个节点及其下游邻居（根据此文）。我开始认为我需要放弃这种做法，而是单独存储边缘。您有什么存储格式建议，可以使这些依赖关系比较更容易吗？ - Scott

@vfxcode - 如果每个节点都有一个上游父节点列表可能会有所帮助。 - hugomg

实际上，根据missingno的建议，给定节点的父节点列表将有助于检查正在迭代的节点是否具有进一步的入边。如果没有，则将其插入到列表S中。我指的是维基百科页面中概述的拓扑排序算法。 - Nadir Muzaffar

我猜最后一件让我困惑的事情（抱歉）是遍历的方向。由于我正在检查已知输入，所以我是在向上游走，随机检查节点还是向下游走？ - Scott

我不太确定你的意思，但在这个算法中，你首先从源节点S（即“顶部”）的列表开始。然后枚举S。当枚举给定元素s时，您会删除所有边缘（s，v），其中v是s的“子项”。如果v不再具有传入边缘（您在此检查上一级别），则将v添加到S中。 - Nadir Muzaffar

Answer 2

你需要通过拓扑排序来处理节点。排序不一定唯一，因此可能有多个可用的顺序（无论如何，这都不重要）。

链接的维基百科页面应该有具体的算法可以帮助你。

- hugomg

---

谢谢你的回答，Nadir的回答只是稍微详细一些。 :) - Scott