有向グラフが強く接続されているかどうかをチェックするアルゴリズム

StackOverflow https://stackoverflow.com/questions/1434787

質問

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

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

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

役に立ちましたか？

解決

Tarjanの強結合コンポーネントアルゴリズム（または Gabowのバリエーション）はもちろん十分です。強く接続されたコンポーネントが1つしかない場合、グラフは強く接続されます。

どちらも線形時間です。

通常の深さ優先検索の場合と同様に、各ノードのステータスを追跡します。新規、確認済み、まだ開いている（コールスタック内にある）、確認済みおよび完了済みです。さらに、最初にノードに到達したときの深さと、ノードから到達可能なそのような最小の深さを保存します（ノードの終了後にこれを知っています）。到達可能な最低の深さがその深さに等しい場合、ノードは強く接続されたコンポーネントのルートになります。これは、ルートからノードに到達する深さが最小ではない場合でも機能します。

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

他のヒント

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

  1. グラフのランダムな頂点vで開始Gし、DFS(G, v)を実行します。

    • uがグラフDFSの他のすべての頂点に到達しない場合、O(n + m)からO(2(n + m)) = O(n + m)への有向パスが存在しないなど、いくつかの頂点<=>が存在するため、 <=>は強く接続されていません。

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

  2. 有向グラフのすべてのエッジの方向を反転<=> 。

  3. 再度<=>から<=>を実行します。

    • DFSがすべての頂点に到達できない場合、元のグラフでは<=>から<=>への有向パスが存在しないなど、いくつかの頂点<=>があります。

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

したがって、G <！> quot; passes <！> quot;両方のDFSが強く接続されています。さらに、DFSは<=>時間で実行されるため、このアルゴリズムは2つのDFSトラバーサルを必要とするため、<=>時間で実行されます。

すべてのノードが、指定されたグラフ内の他のすべてのノードとの両方のパスを持っているかどうかを確認するには：

1。すべてのノードからのDFS / BFS：

Tarjanのアルゴリズムは、すべてのノードに深さd[i]があることを前提としています。最初、ルートの深さは最小です。そして、d[i] = min(d[j])のすべてのネイバーjに対してポストオーダーDFS更新iを行います。実際には、BFSはuこちらの削減ルールでも正常に動作します。

function dfs(i)
    d[i] = i
    mark i as visited
    for each neighbor j of i: 
        if j is not visited then dfs(j)
        d[i] = min(d[i], d[j])

vからd[u] <= d[v]への転送パスがある場合、d[v] <= d[u] <= d[v]。 SCCでは、<=>であるため、SCCのすべてのノードの深さは同じになります。グラフがSCCかどうかを判断するために、すべてのノードが同じ<=>を持っているかどうかを確認します。

2。単一ノードからの2つのDFS / BFS：

Kosaraju <！>＃8217; sアルゴリズムの簡略版です。ルートから開始して、すべてのノードにDFS / BFSが到達できるかどうかを確認します。次に、すべてのエッジの方向を逆にします。すべてのノードが同じルートから再び到達できるかどうかを確認します。 C ++コードを参照してください。

すべてのペアの最短パスを計算して、無限であるかどうかを確認できます。 。

Tarjanのアルゴリズムはすでに言及されています。しかし、グラフの2回のトラバースが必要な場合でも、 Kosarajuのアルゴリズムをフォローする方が簡単です。 。 IIRC、CLRSでも十分に説明されています。

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
}

これを行う1つの方法は、グラフのラプラシアン行列を生成してから、固有値を計算し、最後にゼロの数を数えます。ゼロの固有値が1つだけ存在する場合、グラフは強いつながりがあります。

注：有向グラフのラプラシアン行列を作成するためのわずかに異なる方法に注意してください。

コサラジュ<！>＃8217; sのDFSベースのシンプルなアルゴリズムを使用できます。これは、グラフの2つのDFSトラバーサルを実行します。

アイデアは、すべてのノードが頂点vから到達でき、すべてのノードがvに到達できる場合、グラフは強く接続されます。 アルゴリズムのステップ2では、すべての頂点がvから到達可能かどうかを確認します。ステップ4では、すべての頂点がvに到達可能かどうかを確認します（逆グラフでは、すべての頂点がvから到達可能であれば、すべての頂点は元のvグラフ）。

アルゴリズム： 1）すべての頂点を未訪問として初期化します。

2）任意の頂点vから開始してグラフのDFSトラバーサルを実行します。DFSトラバーサルがすべての頂点にアクセスしない場合は<！>＃8217; t、falseを返します。

3）すべてのアークを逆にします（またはグラフの転置または逆を見つけます）

4）すべての頂点を逆グラフで未訪問としてマークします。

5）同じ頂点vから逆グラフのDFSトラバーサルを開始します（手順2と同じ）。 DFSトラバーサルが<！>＃8217; tすべての頂点にアクセスしない場合、falseを返します。それ以外の場合はtrueを返します。

時間の複雑さ：グラフが隣接リスト表現を使用して表される場合、上記の実装の時間の複雑さはO（V + E）である深さ優先検索と同じです。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top