算法的無環向圖

Question

我正在尋找一個優雅的Python程序，做一個DAG的BFS traveral的BFS traveral：

節點A連接到B（A->B）如果A「依賴於」 B （根據「Bar：Foo-> Bar」思考python包Foo「）。

在大約7000個這樣的節點的圖中，我想排序所有可能的(i, j)，其中1>=i<j<=7000 .. depends(Ni, Nj)爲False的所有節點。取決於（A，B）= True當且僅當A->B或A「取決於」B ..並且Nx是在排序列表中第x位置發生的節點。

注意：節點可以有多個父節點。例如：A-> C和B-> C。因此，根據上述排序規則，A和B必須在C之前出現。

Answer 1

如果我正確地閱讀問題，看起來好像你想要一個topological sort。用於這樣做的最有效的算法（O（V + E））由Tarjan提出，Python實現可以被找到here。

題外話，但似乎你的包依賴類比倒轉;我會認爲「A取決於B」意味着「B-> A」，但是這當然不會改變樹的結構，只是將其顛倒。