データ構造とアルゴリズム - グラフ理論: 連結成分と強連結成分の検出

無向グラフの連結成分を見つける

深さ優先探索を使用すると、グラフのすべての接続コンポーネントを簡単に見つけることができます。接続グラフの概念を思い出してください。任意の頂点から任意の頂点へのパスがある場合、そのグラフは接続グラフと呼ばれます。接続コンポーネントとは、グラフ内のすべての最大接続サブグラフを指します。グラフ全体を数珠つなぎに例えると、頂点を 1 つ持ち上げると、連結されたグラフは 1 つの全体になります。連結されていないグラフは、いくつかの小さな全体に分散され、それぞれの全体がグラフ全体の連結されたコンポーネントになります。連結グラフには連結成分が 1 つだけ、つまりグラフ自体があることは簡単にわかります。グラフの頂点が散在している場合、連結成分 (頂点は 1 つだけ) の数はグラフ内の頂点の数になります。したがって、連結成分の数は[1, graph.vertexNum]の範囲になります。

[[209930]]

下の図には 3 つの接続されたコンポーネントがあります。

深さ優先探索のプロセスを思い出してください。頂点から始まり、その隣接点の 1 つを訪問し、次にこの隣接点の隣接点の 1 つを訪問します... というように、頂点に到達して周囲の隣接点がすべて訪問されたことがわかるまで続きます。この時点で、前の頂点に戻り、その頂点のまだ訪問していない隣接点を訪問します... すべての頂点が訪問されるまで、これを繰り返します。深さ優先のトラバーサルでは、訪問されたすべての頂点が相互に到達可能である、つまり接続されていることが簡単にわかります。 Union-Find アルゴリズムと同様に、各接続コンポーネントに ID のラベルを付けます。つまり、同じ ID を持つ頂点は同じ接続コンポーネントに属します。上で分析したように、連結成分の数は [1, graph.vertexNum] の範囲にあるため、必要な ID の数は graph.vertexNum であり、ID を格納する ID 配列 int[] の範囲は [0, graph.vertexNum – 1] です。

以下は、無向グラフのすべての接続コンポーネントを見つけるためのコードです。使用される無向グラフは、3 つの接続コンポーネントを持つ上記のグラフです。

パッケージChap7; 
 
 java.util.LinkedList をインポートします。 
 
パブリッククラスCC {
    // 各頂点値が 1 回ずつ訪問されたことを確認するために、訪問された頂点をマークするために使用されます
    プライベートブール値[]がマークされています。
    // 接続されている各コンポーネントにIDを付ける
    プライベートint [] id;
    // 接続されたコンポーネントの数
    プライベートint  カウント; 
 
パブリックCC(UndiGraph<?>グラフ) {
        マーク = 新しいブール値[graph.vertexNum()];
        id = 新しいint [graph.vertexNum()];
 ( int s = 0; s < graph.vertexNum(); s++) {
            if (!マークされている[s]) {
                dfs(グラフ, s);
                // dfs 呼び出しは接続されたコンポーネントであり、最初の接続されたコンポーネントの ID は 0 です。
                // 後で割り当てられる ID は増加する必要があります。2 番目に接続されたコンポーネントの ID は 1 で、以下同様です。
カウント++;
            }
        }
    } 
 
    プライベートvoid dfs(UndiGraph<?> グラフ、 int v) {
        // 訪問した頂点のフラグを設定します
        マーク[v] = true ;
        id[v] =カウント;
        // v のすべての隣接頂点からまだ訪問されていない頂点を選択します
( int w : graph.adj(v))の場合{
            if (!マーク[w]) {
                dfs(グラフ、w);
            }
        }
    } 
 
パブリックブール接続( int v, int w) {
 id[v] == id[w]を返します。
    } 
 
公共  int id( int v) {
 id[v]を返します。
    } 
 
公共 整数 カウント（）{
戻る カウント;
    } 
 
公共 静的void main(String[] args) {
        // サイド
int [][] エッジ = {{0, 6}, {0, 2}, {0, 1}, {0, 5},
                {3, 4}, {3, 5}, {4, 5}, {4, 6}, {7, 8},
                {9, 10}、{9, 11}、{9, 12}、{11, 12}}; 
 
        UndiGraph<?> グラフ = new UndiGraph<>(13, エッジ);
        CC cc = 新しいCC(グラフ);
        // Mは連結成分の数です
int M = cc.count ( );
        システム.out.println (M + "接続されたコンポーネント" );
        LinkedList< Integer >[] コンポーネント = (LinkedList< Integer >[]) 新しい LinkedList[M];
 ( int i = 0; i < M; i++)の場合{
            コンポーネント[i] = 新しいLinkedList<>();
        }
        // 同じIDを持つ頂点を同じリンクリストに割り当てる
( int v = 0; v < graph.vertexNum(); v++)の場合{
            コンポーネント[cc.id(v)]. add (v);
        }
        // 各接続コンポーネントの頂点を出力します
( int i = 0; i < M; i++)の場合{
 ( int v : コンポーネント[i]) {
                System.out.print (v+ " " ) ;
            }
            System.out.println( ) ;
        }
    } 
 
 }

プログラムは以下の情報を出力します

3 つの接続コンポーネント
0 1 2 3 4 5 6
 7 8
 9 10 11 12

上の写真と比べてみてください、一致しています！

深さ優先探索の応用 - 無向グラフに閉路があるかどうかを判定する

DFS を使用すると、無向グラフがサイクルであるかどうかを簡単に判断できます (自己ループと平行エッジがないと仮定)。

パッケージChap7; 
 
パブリッククラスUndirectCycle {
    プライベートブール値 marked[];
    プライベートブール値hasCycle; 
 
パブリックUndirectCycle(UndiGraph<?>グラフ) {
        マーク = 新しいブール値[graph.vertexNum()];
 ( int s = 0; s < graph.vertexNum(); s++) {
            if (!マークされている[s]) {
               // 最初は頂点が訪問されていないため、現在訪問している頂点と最後に訪問した頂点が開始点として設定されます。 dfsが再帰的に1回呼び出されると、現在アクセスされているパラメータvはsの隣接点であり、最後にアクセスされたパラメータuはsであり、これは次式を満たします。
                dfs(グラフ, s, s);
            }
        }
    }
    // 修正DFS、vは現在訪問中の頂点を表し、uは最後に訪問した頂点を表します
    プライベートvoid dfs(UndiGraph<?> グラフ、 int v、 int u) {
        // 訪問した頂点のフラグを設定します
        マーク[v] = true ;
        // v のすべての隣接頂点からまだ訪問されていない頂点を選択します
( int w : graph.adj(v))の場合{
            if (!マーク[w]) {
                dfs(グラフ, w, v);
            }そうでない場合 (w != u) {
                hasCycle = true ;
            }
        }
    } 
 
パブリックブールhasCycle() {
 hasCycleを返します。
    }
 }

DFS アルゴリズムが若干変更され、最後に訪問した頂点を表す新しいパラメーター u が追加されました。循環があるかどうかを判断する鍵は、else if (w != u) という文です。 w と u が比較されることに注意してください。なぜこのようにしてサイクルが存在すると判断できるのでしょうか? 現在訪問している頂点 v の隣接点 w が以前に訪問されており、最後に訪問した頂点ではない場合、無向グラフにはサイクルが存在します。下の図に示すケースがこれに該当します。

w が訪問され、w == u の場合、サイクルは存在しません。それが下の図の状況です

有向グラフの強く連結した成分を見つける

有向グラフにおいて、2 つの頂点 v と w が互いに到達可能である場合、それらは強く接続されていると言われます。有向グラフ内の任意の 2 つの頂点が強く接続されている場合は、グラフも強く接続されています。

有向サイクルは強い接続性と密接に関連しています。つまり、2 つの頂点が強く接続されるのは、両方が共通の有向サイクル内にある場合のみです。これは簡単に理解できます。v -> w からのパスと w -> v からのパスがある場合、v と w は強く接続されており、これもリング構造であることを示しています。 V 個の頂点を持つ有向グラフには、[1, V] の範囲内にいくつかの強連結成分があります。強連結グラフには 1 つの強連結成分しかありませんが、有向非巡回グラフには V 個の強連結成分があります。

下の図には 5 つの強く連結されたコンポーネントが含まれています。

無向グラフ内の連結成分を計算するのと同様に、有向グラフ内の強連結成分を計算することも深さ優先探索の応用です。このいわゆる Kosaraju アルゴリズムを実装するには、上記のコードに数行追加するだけです。

このアルゴリズムは実装は簡単ですが、理解するのは簡単ではありません。 nullzx によるこのブログ投稿は非常に優れています。これを読んだ後、Kosaraju アルゴリズムの魔法のようなアプローチを理解しました...

上の図は、2 つの強く連結した要素を持つ有向グラフです。強く連結されたコンポーネント間にループは発生しません。そうでない場合、2 つの連結されたコンポーネントは 1 つになり、同じ強く連結されたコンポーネントと見なされます。連結成分が 1 つの頂点に削減されると、上の図は 2 つの頂点を持つ非巡回グラフになり、左側の頂点は右側の頂点を指します。

左側の強く連結されたコンポーネントの任意の頂点から DFS を開始すると、1 回の呼び出しでグラフ内のすべての頂点にアクセスできます。これは主に、2 つの連結されたコンポーネント間の A2 が B3 を指しているためです。逆に、右側の強く連結されたコンポーネントの任意の頂点から深さ優先探索を開始すると、DFS を 2 回呼び出す必要があります。これは、強く連結されたコンポーネントの数とまったく同じであり、DFS が呼び出されるたびに訪問される頂点は、強く連結されたコンポーネント内のすべての頂点です (このステートメントが正しいと仮定すると、この命題の証明は以下で示されます)。たとえば、最初に DFS が呼び出されると、B3、B4、および B5 が訪問されます。これら 3 つの頂点は、右側の強く連結されたコンポーネントのすべての頂点を構成します。逆に、すべての強く接続されたコンポーネントを見つけるには、DFS が頂点を訪問する順序が、B の強く接続されたコンポーネント内の任意の頂点が A の強く接続されたコンポーネント内のすべての頂点よりも前になるようにすれば十分です。あるいは、別の角度から考えてみましょう。接続されたコンポーネントを頂点に減らすと、グラフ全体が非巡回グラフになります。DFS が頂点を訪問する順序は、まず、接続されたコンポーネント (頂点) を指していない頂点を訪問することです。たとえば、上記の A2 は B3 を指しているので、B の頂点を最初に訪問する必要があります。もっと簡単に言うと、DFS は最初に、出次数が 0 の接続コンポーネント (頂点とみなされる) を訪問します。これにより、DFS の呼び出しで同じ接続コンポーネントが再帰的に訪問され、他の接続コンポーネントにはアクセスされなくなります。最初に他のコンポーネントを指すコンポーネント (出次数が 0 ではない) にアクセスすると、DFS は必ず他の接続コンポーネントに入ります。たとえば、接続コンポーネント A は A2 を経由して接続コンポーネント B に入ります。この場合、DFS は複数の強く接続されたコンポーネントを一度にトラバースするため、目的を達成できません。

たとえば、B3、A2、A0、A1、B4、B5 です。この順序で DFS が呼び出されると、DFS が 2 回呼び出されることが保証されます。もちろん、順序は一意ではありません。DFS では、この関係を保証できる共通の順序、つまり逆順が存在します。

いわゆる逆順序は、DFS 再帰呼び出しが返される前に頂点をスタックにプッシュすることによって取得されるシーケンスです。たとえば、再帰呼び出しスタック dfs(s) -> dfs(v) はパス s -> v を表します。v は s より前に戻るため、最初に v が格納され、次に s が格納されます。スタック内の順序は sv です。

それでは、Kosarajuのアルゴリズムのアイデアについてお話ししましょう。

元の画像を反転します。
逆グラフの深さ優先トラバーサルを実行して、頂点の逆順序を取得します。
元の画像に戻り、上記で取得した逆順シーケンスに従って、元の画像に対して深さ優先検索を実行します。 (0、1、2...という頂点の順序に従うのではなく)

逆グラフの逆順が、必要なシーケンスである理由を見てみましょう。

上図は反転後の有向グラフです。元の画像を G、反転した画像を Gr とします。深さ優先探索 Gr には 2 つの可能性があります。

強く連結されたコンポーネント A の任意の頂点から始めて、DFS を 2 回呼び出す必要があります。1 回目は A0、A1、A2 がスタックにプッシュされ、2 回目は B3、B4、B5 がスタックにプッシュされます。この場合、強く連結されたコンポーネント B のすべての頂点は、強く連結されたコンポーネント A の前にあります。
強く接続されたコンポーネント B 内の任意の頂点から開始して、1 つの DFS を呼び出すことですべての頂点をトラバースできます。逆順なので、B で最初に訪問された頂点が最後に返され、スタックの一番上になります。

上記の 2 つの状況では、B の少なくとも 1 つの頂点が A のすべての頂点の前にあることが保証されます。元のグラフに戻ると、最初に B の頂点に対して DFS が実行されます。複数の強く連結されたコンポーネントを持つ有向グラフに拡張しても、上記の推論は依然として当てはまります。

逆グラフの逆順序は、実際には擬似位相シーケンスです (リング構造が存在する可能性があるため、「擬似」です)。接続されたコンポーネントを 1 つの頂点に減らすと、有向グラフは非循環になり、逆グラフの逆順序は位相シーケンスになります。つまり、入次数が 0 の頂点が常に最初にランク付けされます。元のグラフでは、トポロジシーケンスは、出次数 0 の頂点が前に配置されるようになります。上で分析したように、出次数 0 のコンポーネント (すでに頂点と見なされている) に対して最初に DFS を実行すると、頂点にアクセスするために DFS が呼び出されるたびに、それらの頂点が同じ強く接続されたコンポーネントの下にあることが保証されます。

Kosaraju のアルゴリズムの正しさを正確に証明するには、次の命題を証明する必要があります。元のグラフで逆グラフの逆の順序で DFS を実行し、各 DFS で訪問されるすべての頂点が同じ接続コンポーネント内にある。上で述べたことは、逆グラフの逆順のようなシーケンスを使用すると、目的である命題の後半を達成できる理由の定性的な説明にすぎません...上記の分析では、それが正しいと仮定しています。実際には、この命題には厳密な証明が必要です。以下は、前半の前提の下で、命題の後半の正しさを証明することです。

この命題を証明するには、証明すべき点が 2 つあります (逆グラフの逆の順序で DFS を実行するという前提の下)。

s に強く接続されているすべての頂点 v は、dfs(G, s) の呼び出しで訪問される必要があります。
dfs(G, s) が到達する任意の頂点 v は s に強く接続されている必要があります。

まず、背理法を使用します。dfs(G, s) の呼び出しで訪問されない頂点 v があるとします。パス s -> v があるため、dfs(G, s) が呼び出される前に v が訪問されていることを意味します (そうでない場合は仮定と矛盾します)。また、パス v -> s もあるため、dfs(G, v) を呼び出した後、s は確実に訪問済みとしてマークされるため、dfs(G, s) は呼び出されません。これは、dfs(G, s) が呼び出されるという仮定と矛盾します。したがって、元の命題は成立します。

次に、dfs(G, s) は頂点 v に到達できるため、s -> v へのパスがあることがわかります。s と v が強く接続されていることを証明するには、元のグラフ G に v -> s へのパスがあることを証明するだけで済みます。これは、逆グラフ Gr で s -> v へのパスを見つけることと同じです。深さ優先探索は逆順に実行されるため、Gr では dfs(Gr, v) は dfs(Gr, s) の前に返される必要があります。そうでない場合、逆順は [v, s] になります。dfs が呼び出されると、元のグラフでは dfs(G, v) が最初に呼び出されます。このとき、元のグラフにパス v -> s がある場合、dfs(G, v) が呼び出された後、s は訪問済みとしてマークされるため、dfs(G, s) は呼び出されません。これは、dfs(G, s) が呼び出されて v 頂点に到達するという仮定と矛盾しています。したがって、Gr では、dfs(Gr, v) は必ず dfs(Gr, s) の前に戻ります。次の 2 つのケースがあります。

dfs(Gr, v) は dfs(Gr, s) の前に呼び出され、dfs(Gr, s) の呼び出しが終了する前に終了します。つまり、dfs(Gr, v) が呼び出され、-> dfs(Gr, v) が終了し、-> dfs(Gr, s) が呼び出され、-> dfs(Gr, s) が終了します。
dfs(Gr, v) は dfs(Gr, s) の後に呼び出され、dfs(Gr, s) の呼び出しが終了する前に終了します。つまり、dfs(Gr, s)が呼び出される -> dfs(Gr, v)が呼び出される -> dfs(Gr, v)が終了 -> dfs(Gr, s)が終了

最初のケースは不可能です。 Gr には v -> s (および G には s -> v) があるため、最初のケースの呼び出しは不可能です。 2 番目のケースは、Gr に s -> v へのパスが存在することを示しています。実証済み！

下図に示すように、中央と右の図は上記の 2 つの状況に対応しています。

この証明は、コードを与えるべきであることも証明しています。

パッケージChap7; 
 
 java.util.LinkedList をインポートします。 
 
 /**
 * 有向グラフ内の強く連結したコンポーネントを見つける
 */
パブリッククラスKosarajuSCC {
    // 各頂点値が 1 回ずつ訪問されたことを確認するために、訪問された頂点をマークするために使用されます
    プライベートブール値[]がマークされています。
    // 接続されている各コンポーネントにIDを付ける
    プライベートint [] id;
    // 接続されたコンポーネントの数
    プライベートint  カウント; 
 
パブリックKosarajuSCC(DiGraph<?>グラフ) {
        マーク = 新しいブール値[graph.vertexNum()];
        id = 新しいint [graph.vertexNum()];
        // 元の画像 G を反転して Gr を取得します
        DFSorder の順序= 新しい DFSorder(graph.reverse());
        // Gr の逆順に dfs を実行します
for ( int s : order .reversePost()) {
            if (!マークされている[s]) {
                dfs(グラフ, s);
                // dfs 呼び出しは接続されたコンポーネントであり、最初の接続されたコンポーネントの ID は 0 です。
                // 後で割り当てられる ID は増加する必要があります。2 番目に接続されたコンポーネントの ID は 1 で、以下同様です。
カウント++;
            }
        }
    } 
 
    プライベートvoid dfs(DiGraph<?> グラフ, int v) {
        // 訪問した頂点のフラグを設定します
        マーク[v] = true ;
        id[v] =カウント;
        // v のすべての隣接頂点からまだ訪問されていない頂点を選択します
( int w : graph.adj(v))の場合{
            if (!マーク[w]) {
                dfs(グラフ, w);
            }
        }
    } 
 
パブリックブール値がstronglyConnected( int v, int w) {
 id[v] == id[w]を返します。
    } 
 
公共  int id( int v) {
 id[v]を返します。
    } 
 
公共 整数 カウント（）{
戻る カウント;
    } 
 
公共 静的void main(String[] args) {
        // サイド
int [][] エッジ = {{0, 1}, {0, 5}, {2, 3},{2, 0}, {3, 2},
                {3, 5}, {4, 2}, {4, 3},{4, 5}, {5, 4}, {6, 0}, {6, 4},
                {6, 9}, {7, 6}, {7, 8}, {8, 9},{8, 7}, {9, 10},
                {9, 11}、{10, 12}、{11, 4}、{11, 12}、{12, 9}}; 
 
        DiGraph<?> グラフ = new DiGraph<>(13, エッジ);
        KosarajuSCC cc = 新しい KosarajuSCC(グラフ);
        // Mは連結成分の数です
int M = cc.count ( );
        システム.out.println (M + "接続されたコンポーネント" );
        LinkedList< Integer >[] コンポーネント = (LinkedList< Integer >[]) 新しい LinkedList[M];
 ( int i = 0; i < M; i++)の場合{
            コンポーネント[i] = 新しいLinkedList<>();
        }
        // 同じIDを持つ頂点を同じリンクリストに割り当てる
( int v = 0; v < graph.vertexNum(); v++)の場合{
            コンポーネント[cc.id(v)]. add (v);
        }
        // 各接続コンポーネントの頂点を出力します
( int i = 0; i < M; i++)の場合{
 ( int v : コンポーネント[i]) {
                システム.out.print (v + " " );
            }
            System.out.println( ) ;
        }
    }
 }

具体的な有向グラフについて、Kosaraju のアルゴリズムの軌跡を見てみましょう。左の図は逆グラフのDFSであり、逆順の並びが擬似位相シーケンスとなっている。右の図では、元の有向グラフをこのシーケンスに従ってDFSし、合計5つの頂点をDFSしている。各DFSは、強連結成分（四角で囲まれた頂点の集合）を表している。

[画像のアップロードに失敗しました...(image-f58914-1510374691562)]

上記のコードのテスト例は、実際には上記の画像です。以下の情報が印刷されます

5 つの接続コンポーネント
1
 0 2 3 4 5
 9 10 11 12
 6
 7 8

上の図のボックスで囲まれた内容と比較すると、確かに強く連結されたコンポーネントが 5 つあります。

ちなみに、グラフ内の強く連結された要素を 1 つの頂点に減らすと、次のグラフが得られます。強く接続されたコンポーネント間にループは存在しないため、逆の順序は真のトポロジカルシーケンスになります。元の有向グラフに戻り、トポロジーシーケンス（順序は 1、0、11、6、7）に従って DFS を実行します。アルゴリズムは常に出次数 0 の頂点を優先し、DFS 後に頂点を削除し、残りのグラフから出次数 0 の頂点を選択して DFS を続行することがわかります。

このアルゴリズムを分析するのは面倒だと思います...面倒くさければ、結論だけ覚えておいてください。

<<: BaiduのNLP自然言語処理技術の最も包括的な分析

>>: AI、ブロックチェーン、ロボット：テクノロジーは仕事の未来をどのように変えるのでしょうか？