16

有向グラフが強く接続されているかどうか、つまり、他のノードがすべてのノードに到達できるかどうかを確認する必要があります（必ずしも直接エッジを経由する必要はありません）。

これを行う1つの方法は、すべてのノードでDFSとBFSを実行し、他のすべてのノードがまだ到達可能であることを確認することです。

それを行うためのより良いアプローチはありますか？

4

9 に答える 9

32

次のアルゴリズムを検討してください。

  1. vグラフのランダムな頂点から始めてG、DFS(G, v).

    • DFS(G, v)グラフ内の他のすべての頂点に到達できない場合は、 からへの有向パスがなく、したがって強く接続されていないような頂点がいくつGかあります。uvuG

    • vすべての頂点に到達する場合、グラフ内の他のすべての頂点への有向パスがありますG。

  2. 有向グラフのすべてのエッジの方向を逆にしますG。

  3. DFSで始まるa を再度実行しvます。

    • DFS がすべての頂点に到達できない場合u、元のグラフには からuへの有向パスがないような頂点 が存在しvます。

    • 一方、すべての頂点に到達する場合、元のグラフにはすべての頂点から への有向パスがありuvます。

したがって、G が両方の DFS を「通過」する場合、強く接続されています。さらに、DFS はO(n + m)時間内に実行されるため、このアルゴリズムはO(2(n + m)) = O(n + m)時間内に実行されます。これは、2 つの DFS トラバーサルが必要になるためです。

于 2012-10-17T19:28:18.410 に答える
18

もちろん、 Tarjan の強連結成分アルゴリズム (またはGabow のバリエーション) で十分です。強連結成分が 1 つしかない場合、グラフは強連結です。

どちらも線形時間です。

通常の深さ優先検索と同様に、各ノードのステータスを追跡します: 新規、認識済みだがまだ開いている (コール スタック内にある)、認識済みで終了済み。さらに、最初にノードに到達したときの深さと、そのノードから到達可能な最も低い深さを保存します (これは、ノードを終了した後でわかります)。ノードは、到達可能な最小深度がそれ自体の深度と等しい場合、強連結コンポーネントのルートです。これは、ルートからノードに到達する深さが最小でなくても機能します。

グラフ全体が単一の SCC であるかどうかを確認するには、任意の単一ノードから dfs を開始します。終了時に、到達可能な最小深度が 0 で、すべてのノードが訪問された場合、グラフ全体が強く接続されています。

于 2009-09-16T18:54:51.327 に答える
1 
test-connected(G)
{
    choose a vertex x
    make a list L of vertices reachable from x,
    and another list K of vertices to be explored.
    initially, L = K = x.

    while K is nonempty
    find and remove some vertex y in K
    for each edge (y, z)
    if (z is not in L)
    add z to both L and K

    if L has fewer than n items
    return disconnected
    else return connected
}
于 2010-09-18T05:19:42.573 に答える
1

All-Pairs Shortest Pathを計算して、無限パスがあるかどうかを確認できます。

于 2009-09-16T18:55:08.877 に答える
0

これを行う1つの方法は、グラフのラプラシアン行列を生成し、固有値を計算して、最後にゼロの数を数えることです。ゼロ固有値が1つしかない場合、グラフは強く関連しています。

注：有向グラフのラプラシアン行列を作成する方法が少し異なることに注意してください。

于 2009-09-16T18:58:38.890 に答える