10

私はBFSとDFSに関するグラフアルゴリズムを読んでいました。DFSを介してグラフ内の強連結成分を見つけるためのアルゴリズムを分析していたとき、疑問が浮かびました。強く接続されたコンポーネントを見つけるために、book（Coremen）は、最初に頂点の終了時間を取得するためにグラフ上でDFSを実行し、次に終了時間の降順でグラフの転置に対してDFSを実行しました。これは最初のDFSから取得しました。しかし、なぜ2番目のDFSを終了時間に従って実行する必要があるのか​​理解できません。つまり、グラフの転置で（終了時間を無視して）DFSを直接実行したとしても、転置を実行することで他のコンポーネントへのパスがすでにブロックされているため、接続されたコンポーネントを取得できた可能性があります。

4

1 に答える 1

16

編集 - このトピックに関するスタンフォード大学の優れた詳細なビデオを次に示します。

http://openclassroom.stanford.edu/MainFolder/CoursePage.php?course=IntroToAlgorithms (6. 有向グラフの接続性を参照)

私の説明：

最初の dfs の終了時間の短縮に従って 2 番目の dfs を実行しないと、グラフ全体を単一の強連結成分 (SCC) として誤って識別する可能性があります。

ここに画像の説明を入力

私の例では、ノードdは最初の dfs からの終了時間が常に最も短いことに注意してください。ノードa、b、またはのいずれかcの終了時間が最も長くなります。の終了時間が最も長いと仮定しaて、終了時間の減少に従って 2 番目の DFS を実行するaと、最初になります。

dここで、 の転置でnode から始まる 2 番目の dfs を実行するGと、グラフ全体を含む深さ優先フォレストが生成され、グラフ全体が SCC であると結論付けられますが、これは明らかに誤りです。ただし、 で dfs を開始すると、 、、およびが SCC であることがわかるaだけでなく、重要な部分は、グレーまたは黒に着色されてアクセス済みとしてマークされることです。次に、 で dfs を続行すると、隣接するノードが訪問されたことに気付くため、SCC から出ることはありません。abcd

DFS の cormens コードを見ると、

DFS(G)
1 for each vertex u in G.V
2     u.color = WHITE
3     u.π = NIL
4 time = 0
5 for each vertex u in G.V
6     if u.color == WHITE
7         DFS-VISIT(G, u)

DFS-VISIT(G, u)
1 time = time + 1 // white vertex u has just been discovered
2 u.d = time
3 u.color = GRAY
4 for each v in G.adj[u]
5     if v.color == WHITE
6         v.π = u
7         DFS-VISIT(G, u)
8 u.color = BLACK // blacken u; it is finished
9 time = time + 1
10 u.f = time

終了時間の減少を使用しなかった場合、DFS-VISIT はグラフ全体を再帰的に参照するため、DFS の 6 行目は 1 回だけ true になります。これにより、深さ優先フォレストに 1 つのツリーが生成され、各ツリーは SCC になります。ツリーが 1 つの理由は、ツリーはそのルート ノードが nil の先行ノードを持つことによって識別されるためです。

于 2012-12-07T19:15:49.290 に答える