graph - 有向无环图遍历...帮助？

Question

有点超出我的深度，需要给朋友打电话。我有一个需要遍历的有向无环图，并且我第一次跌跌撞撞地进入图论。我最近读了很多关于它的书，但不幸的是我没有时间在学术上弄清楚这一点。有人可以帮我解决如何处理这棵树的问题吗？

以下是规则：

• 有n 个根节点（我称它们为“源”）
• 有n个端节点
• 源节点带有一个数值
• 下游节点（我称它们为“工作”节点）对传入的值执行各种操作，如 Add、Mult 等。

从下图中可以看出，节点a、b、 和c需要在d、e、 或之前进行处理f。

走这棵树的正确顺序是什么？

Answer 1

我会研究 DAG 的线性化，这应该可以通过拓扑排序来实现。

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

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

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

Answer 2

您需要通过Topological sort处理节点。排序不一定是唯一的，因此可能有多个可用的订单（无论如何这都不重要）。

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