python - 无环有向图的 BFS 遍历算法

Question

我正在寻找一个优雅的 Python 程序，它对 DAG 进行 BFS 遍历：

如果 A“依赖于”B，则节点 A 连接到 B ( A->B)（想想 python 包 Foo “依赖于”Bar: Foo->Bar）。

在大约 7000 个这样的节点的图中，我想对所有节点进行排序，以便在所有可能的情况(i, j)下1>=i<j<=7000..depends(Ni, Nj)为 False。depends(A, B) = True 当且仅当A->B或 A“依赖于” B .. 并且是出现在排序列表中第 th 位Nx的节点。x

注意：一个节点可以有多个父节点。例如：A->C 和 B->C。因此，根据上述排序规则，A 和 B 必须在 C 之前。

Answer 1

如果我正确阅读了这个问题，那么您似乎想要一个拓扑排序。Tarjan提出了最有效的算法 (O(V+E))，可以在此处找到 Python 实现。

题外话，但似乎你的包依赖类比是颠倒的；我认为“A 依赖于 B”意味着“B->A”，但这当然不会改变树的结构，只是将其反转。