无环有向图的广度优先搜索算法

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)为真，仅当A->B或者A“依赖于”B时成立，而Nx是排序列表中第x个位置的节点。

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

Answer 1

如果我理解你的问题没错的话，你想要的是一种叫做拓扑排序的方法。最有效的算法（时间复杂度是O(V+E)）是由塔尔詹提出的，你可以在这里找到它的Python实现。

题外话，你提到的包依赖关系似乎有点反了；我觉得“ A依赖于B”应该意味着“B->A”，不过这并不会改变树的结构，只是把它反过来了。