16

私は独学でグラフ理論を試しており、グラフでSCCを見つける方法を理解しようとしています。SO に関するいくつかの異なる質問/回答 (例: 1、2、3、4、5、6、7、8 ) を読みましたが、従うことができる完全なステップバイステップの例を含むものを見つけることができません。

CORMEN (Introduction to Algorithms)によると、1 つの方法は次のとおりです。

  1. DFS(G) を呼び出して、各頂点 u の終了時刻 f[u] を計算します
  2. 転置計算(G)
  3. DFS(Transpose(G)) を呼び出しますが、DFS のメイン ループでは、(ステップ 1 で計算されたように) f[u] が減少する順序で頂点を考慮します。
  4. ステップ 3 の深さ優先フォレスト内の各ツリーの頂点を個別の強連結成分として出力します。

次のグラフを観察してください (質問はここから 3.4です。こことここでいくつかの解決策を見つけましたが、これを分解して自分で理解しようとしています。)

ここに画像の説明を入力

ステップ 1: DFS(G) を呼び出して、各頂点 u の終了時刻 f[u] を計算する

頂点 A から開始する DFS の実行:

ここに画像の説明を入力

[Pre-Vist, Post-Visit] としてフォーマットされた赤いテキストに注意してください。

ステップ 2: Transpose(G) を計算する

ここに画像の説明を入力

ステップ 3. DFS(Transpose(G)) を呼び出しますが、DFS のメイン ループでは、(ステップ 1 で計算したように) f[u] の降順で頂点を考慮します。

では、訪問後 (終了時間) の値が減少する順に頂点を示します。

{E、B、A、H、G、I、C、D、F、J}

したがって、このステップでは、G^T で DFS を実行しますが、上記のリストの各頂点から開始します。

  • DFS(E): {E}
  • DFS(B): {B}
  • DFS(A): {A}
  • DFS(H): {H、I、G}
  • DFS(G): すでに訪問されているため、リストから削除します
  • DFS(I): すでに訪問されているため、リストから削除します
  • DFS(C): {C、J、F、D}
  • DFS(J): すでに訪問されているため、リストから削除します
  • DFS(F): すでに訪問されているため、リストから削除します
  • DFS(D): すでに訪問されているため、リストから削除します

ステップ 4: ステップ 3 の深さ優先フォレスト内の各ツリーの頂点を個別の強連結成分として出力します。

したがって、{E}、{B}、{A}、{H、I、G}、{C、J、F、D} の 5 つの強連結成分があります。

これが私が正しいと信じていることです。ただし、こことここで見つけた解決策では、SCC は {C、J、F、H、I、G、D} および {A、E、B} であると言われています。私の間違いはどこですか？

4

2 に答える 2

0

あなたの手順は正しく、答えも正しいです。提供した他の回答を調べると、別のアルゴリズムが使用されていることがわかります。最初に転置された G で DFS を実行し、次に頂点を減少させて処理する G で無向コンポーネント アルゴリズムを実行します。前のステップからの投稿番号の順序。

問題は、彼らが G ではなく転置された G でこの最後のステップを実行したため、誤った答えが得られたことです。Dasgupta の 98 ページ以降を読むと、彼らが (試みた) 使用しようとしたアルゴリズムの詳細な説明が表示されます。

于 2015-11-24T22:32:02.417 に答える