有向グラフで sharir kosaraju アルゴリズムを実行するとします。このグラフにはアーク (u,v) があります。このアルゴリズムには、2 つの DFS パスがあります。ここで、頂点 u を最初の深さツリー T に挿入するとします。v はどこに現れるでしょうか? 以前または後で作成された別のツリーにありますか? 前もって感謝します ！
私はテストのために学んでいます...これは一種の宿題だと思いますが、私は本当に手がかりがありません!
質問する
1452 次
2 に答える
2
Kosaraju のアルゴリズムは、グラフの転置には元のグラフと同じ数の強連結成分 (SCC) があるという事実に基づいています。
1) グラフ G と空のスタック S があります。
2) S に G のすべてのノードが含まれているわけではありませんが、ランダムな頂点 u を選択し、u に対して DFS を実行します。この DFS 中にノード v の探索が終了したら、ノード v を S にプッシュします。
質問に戻りますが、有向辺 (u,v) がある場合、v は必ず u の前にスタック S に挿入されます。ただし、v の挿入と u の挿入の間にさらに多くのノードが存在する可能性があります。
3) S が空になるまで、スタック S から頂点をポップすることにより、G の転置の DFS を実行します。これにより、グラフ G のすべての SCC が取得されます。
于 2012-04-14T13:33:07.423 に答える
0
ウィキ: http://en.wikipedia.org/wiki/Kosaraju%27s_algorithmは非常に有益です。アルゴリズムを実装しました。こちらから入手できます。
http://khanna111.com/wordPressBlog/2012/04/11/strongly-connected-components-of-a-graph/
最初に理解しておくべきことは、パス後の最初のステップでスタック内の最上位の要素が親になり、2 番目のステップでそれらが先にポップアウトされ、パスで強く接続されたノードで転置に作用することです。元のグラフは、転置で強く接続されたままになります。
最初のパスの全体的な理由は、親をスタックの一番上に置くことです。
于 2014-08-11T04:11:25.503 に答える