问候,
任何人都可以告诉我什么算法用于遍历这样的有向无环图/图:
Ex. Diagram nodes : A, B, C, D1, D2, D3, E
Diagram edges : A → B, B → C, C → D1, C → D2, C → D3, D1 → E, D2 → E, D3 → E
遍历是这样的:
A → B → C → D1, then C → D2, then C → D3,
And after that, they join : D1 → E, D2 → E, D3 → E
我的图表代表实时操作。大多数操作是线性的,但是当操作按条件拆分时,每个拆分(例如节点 C 拆分为 D1、D2 和 D3)在它们再次加入之前等待所有操作完成(例如节点 D1、D2 和 D3 在节点 E 处加入) )
我需要遍历我的节点并按照这个确切的顺序调用每个操作。
我使用 Python 和 pygraph,但如果你想发布一些算法,你可以使用任何语言。
也许这是这个算法的标准名称,比如深度优先搜索、Dijkstra 算法、爬山算法,我不知道?...
非常非常感谢!
最佳答案
A topological sort将为您提供在给定边上执行操作所需的顺序。
关于python - 遍历代表真实操作的图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6156392/