定向非循环图遍历...帮助？
Sco*_*ott 6 traversal graph directed-acyclic-graphs
我的深度有点偏离,需要给朋友打电话.我有一个我需要遍历的定向非循环图,我第一次绊到了图论.我最近一直在阅读很多关于它的内容,但不幸的是我没有时间在学术上解决这个问题.有人可以帮我解决一下如何处理这棵树吗？
以下是规则:
- 有n个根节点(我称之为"源")
- 有n个终端节点
- 源节点带有数值
- 下游节点(我称之为"工作"节点)对传入值(如Add,Mult等)执行各种操作.
正如你可以看到下面的图,节点a,b和c需要被处理之前d,e或f.
走这棵树的顺序是什么？
我将研究DAG的线性化,这应该可以通过拓扑排序实现.
从我记忆中看,线性化基本上按顺序排序,该顺序保持不变,对于所有节点(Node_X),其具有与任何其他给定节点的outdegree NodeA,NodeX之前出现NodeA.
这意味着,从您的示例中,将首先处理节点a,b和d.节点c秒.节点e和f,最后.
http://en.wikipedia.org/wiki/Topological_sorting
- @vfxcode - 如果每个节点都有一个上游父节点列表,它可能会有所帮助. (2认同)