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)是假的。 depends(A, B) = True 当且仅当 A->B或 A“取决于”B .. 和 Nx是出现在 x 中的节点吗？排序列表中的第 th 个位置。

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

Answer 1

如果我没看错问题，看起来你想要一个 topological sort . Tarjan 提出了最有效的算法 (O(V+E)) ，并且可以找到 Python 实现 here .

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