python - 非環状有向グラフの BFS 走査のアルゴリズム

Question

DAG の BFS 走査を行うエレガントな Python プログラムを探しています。

A が B に「依存」している場合、ノード A は B ( A->B) に接続されます (Python パッケージ Foo が「Bar: Foo->Bar に依存している」と考えてください)。

このような約 7000 のノードのグラフで、すべてのノードを並べ替えて、.. が False になるようにしたいと考えて(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

質問を正しく読んでいる場合、トポロジカルソートが必要なようです。これを行うための最も効率的なアルゴリズム (O(V+E)) は、Tarjanによって提案されました。Pythonの実装は、ここにあります。

トピックから外れていますが、パッケージの依存関係の類推が逆になっているようです。「A は B に依存する」は「B->A」を意味すると思いますが、もちろん、これはツリーの構造を変更するのではなく、単に逆にするだけです。