algorithm - 特定のノードの依存関係を見つけるためのトポロジカル ソート

Question

次のグラフを考えると：

特定のノードにのみ関連する、完了すべきタスクを含むトポロジー順序リストを出力するために使用できるアルゴリズムは何ですか?

たとえば、 を考慮するnode 2と、リストは次のようになります。

7, 5, 11, 2

また

5, 7, 11, 2

Answer 1

1. エッジを反転します
2. から開始してDFSを実行します2
3. ノードを離れたら、それをリストに挿入します。

例：

Enter 2
  Enter 11
    Enter 7
    Leave 7, insert into list
    Enter 5
    Leave 5, insert into list
  Leave 11, insert into list
Done, insert 2 into list

Result: 7, 5, 11, 2

Answer 2

グラフを隣接行列に分解する必要があります。この行列では、ノード A からノード B へのすべてのリンクがノードと列に対応する行列で「1」として表されます。

この時点から、端末ノードから逆方向に作業し、それを指しているノードを特定し、それらのそれぞれから逆方向に作業するだけです。

ここで、おそらくこれを幅優先の方法で行いたいと思うので、キュー データ構造を使用して「依存」ノードを追跡します。