15

ウィキペディアから 3 時間かけてタージャンのアルゴリズムを学ぼうとしてきましたが、頭も尻尾もわかりません。:(

http://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm#cite_note-1

なぜ DFS ツリーのサブツリーなのですか? (実際、DFS はフォレストを生成しますか? o_O) そして、なぜそれがルートであるv.lowlink=v.indexことを意味するのでしょうか?v

誰かが私にこれを説明してくれますか/このアルゴリズムの背後にある直感や動機を教えてください。

4

4 に答える 4

15

アイデアは次のとおりです。ツリーをトラバースするとき、ブランチを検索してバックトラックするたびに、ツリーの「上位」ノードへのエッジに遭遇したかどうかを確認します。

  • ( ) を行っていない場合はif (v.lowlink = v.index)、SCC を完了したことになります。これは、現在のノードとスタック上のすべてのノードで構成されています。これは、すでに完了した SCC のノードを除いて、まさに DFS ツリーのサブツリーです。

  • 実行した場合は、この情報を「上位」ノード ( v.lowlink := min(v.lowlink, w.lowlink)) に伝達します。これは、エッジが DFS ツリーのパスと組み合わされて「上位」パスを作成するためです。

DFS はフォレストを生成しますが、一度に 1 つのツリーを常に考慮します。SCC は常に 1 つの DFS ツリーに含まれます。それ以外の場合 (SCC である場合)、問題の両方の (すべての) ツリー間に双方向のパスが存在します。これは矛盾です。

于 2012-06-13T14:03:06.167 に答える
11

pjotrの答えに追加するだけです。v.lowlinkは基本的に、ツリーで見つけた最上位ノードのインデックスです。このコンテキストでの最上部は、歩きながらインデックスを増やし続けるため、最小を意味することに注意してください。すべての後継者を処理した後、基本的に3つのケースがあります。

  1. v.lowlink <v.index：これはバックエッジが見つかったことを示します。バックエッジが見つかっただけでなく、現在のノードの「上」にあるノードを指していることに注意してください。それがv.lowlink<v.indexが意味することです。

  2. v.lowlink = v.index：この場合、現在のノードの上にあるものを参照するバックエッジがないことがわかります。このノードにはバックエッジがある可能性があります（つまり、後続ノードwの1つに、w.lowlink = v.lowlink = v.indexのようなローリンクがあります）。また、現在のノードの下にあるものを参照するバックエッジがあった可能性もあります。これは、現在のノードの下に、すでに印刷されている強連結成分があったことを意味します。ただし、現在のノードは、確実に強連結成分のルートでもあります。

  3. v.lowlink> v.index：それは実際には不可能です。完全を期すためにリストしているだけです。;）

それが役に立てば幸い！

于 2013-02-25T21:46:17.800 に答える