一种acylic有向图的BFS遍历算法

Question

我正在寻找一个优雅的Python程序,可以完成BFS的几个DAG:

A->B如果A"依赖于"B(考虑到python包Foo"取决于"Bar:Foo-> Bar),则节点A连接到B().

在约7000个这样的节点图,我想这样的,对于所有可能的所有节点进行排序(i, j),其中1>=i<j<=7000.. depends(Ni, Nj)是假.depends(A,B)= True当且仅当A->B或"A"依赖于"B .."并且Nx是x在排序列表中的位置出现的节点.

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

Answer 1

如果我正确地阅读问题,看起来你想要拓扑排序.Tarjan提出了最有效的算法(O(V + E)),可以在这里找到Python实现.

偏离主题,但似乎你的包依赖类比是相反的; 我认为"A取决于B"意味着"B-> A",但当然这不会改变树的结构,只会改变它.