グラフアルゴリズムシリーズにおける深さ優先探索

[[396433]]

この記事はWeChatの公開アカウント「Beta Learns JAVA」から転載したもので、著者はSilently9527です。この記事を転載する場合は、Beta Learning JAVA パブリックアカウントにお問い合わせください。

前回の記事では、深さ優先探索と、深さ優先探索を使用してグラフ内のパスを見つける方法について学習しました。この記事では、深さ優先探索アルゴリズムの他の適用シナリオについて引き続き学習します。

接続されたコンポーネント

グラフからすべての接続コンポーネントを見つけることも、深さ優先探索の応用シナリオです。連結成分とは何でしょうか? この定義は、前回の記事「ソーシャルネットワークで 2 人の人が友人であるかどうかを検出する方法 (結合検索アルゴリズム)」で説明しました。

この記事では、結合検索アルゴリズムによって接続性チェックを実装します。この記事では、深さ優先探索法を使用して、グラフ内のすべての接続コンポーネントを検索します。

接続コンポーネントのAPI定義

パブリッククラスDepthFirstCC {
パブリックDepthFirstCC(グラフ グラフ); 
     
 public boolean connected( int v, int w); // 2つの頂点が接続されているかどうかを確認します
 
公共 整数  count (); //接続されたコンポーネントの合計数をカウントします
 
公共  int id( int v); //頂点vが位置する接続コンポーネントの識別子
}

接続コンポーネントのAPI実装

以前と同様に、頂点をスキャンしない場合はマークする必要があるため、marked[]配列を定義する必要があります。

グラフ内の連結成分の総数を数えるには、変数countを定義する必要がある。

2 つの頂点が接続されているかどうかを判断するには、接続されている頂点の対応する識別値を同じ値として記録する必要があります。接続メソッドを呼び出すときに、2 つの頂点の識別値を直接取り出して比較します。同じ場合は接続されており、そうでない場合は接続されていません。

使用する識別値はカウント値です。各頂点には識別値を格納する必要があるため、ids[]配列も必要です。

パブリッククラスDepthFirstCC {
    プライベートブール値 marked[];
    プライベートint  カウント;
    プライベートint [] ids; 
 
パブリックDepthFirstCC(グラフグラフ) {
        this.marked = 新しいブール値[graph.V()];
        this.ids = 新しいint [graph.V()]; 
 
 ( int v = 0; v < graph.V(); v++)の場合{
            if (!this.marked[v]) {
                dfs(グラフ, v);
カウント++;
            }
        }
    } 
 
    プライベートvoid dfs(グラフグラフ、 int v) {
        this.marked[v] = true ;
        this.ids[v] =カウント;
 ( int w : graph.adj(v))の場合{
            if (!this.marked[w]) {
                dfs(グラフ, w);
            }
        }
    } 
 
パブリックブール接続( int v, int w) {
 id(v) == id(w)を返します。
    } 
 
公共 整数 カウント（）{
戻る カウント;
    } 
 
公共  int id( int v) {
 ids[v]を返します。
    } 
 
 }

ユニットテスト

このようなグラフを構築すると、連結成分の総数は3になるはずです。

 @テスト
パブリックボイドテスト（）{
    グラフ graph = new Graph(10);
    グラフにエッジを追加します。(0, 1);
    グラフにエッジを追加します(0, 2);
    グラフにエッジを追加します(0, 5);
    グラフにエッジを追加します。(1, 3);
    グラフにエッジを追加します。
    グラフにエッジを追加します(4, 3);
    グラフにエッジを追加します(5, 3); 
 
    グラフにエッジを追加します(6, 7); 
 
    グラフにエッジを追加します(8, 9); 
 
    DepthFirstCC cc = 新しい DepthFirstCC(グラフ); 
 
    System.out.println (cc.connected(0,5)) ;
    System.out.println (cc.connected(1,2)) ; 
 
    System.out.println ( cc.count ()) ;
 }

深さ優先探索に基づく接続性チェックは、理論的には、以前に実装された和集合検索アルゴリズムよりも高速です。これは、深さ優先探索で実装された接続性チェックは一定時間で完了することが保証されるのに対し、和集合検索アルゴリズムではそれができないためです。

しかし、union-find にも独自の利点があります。グラフを完全に構築して表現する必要がなく、さらに重要なことに、union-find アルゴリズムは動的にノードを追加します。

無向グラフにサイクルがあるかどうかを確認する

実装の複雑さを軽減するために、グラフには自己ループや平行エッジが存在しないものと仮定します。

頂点 v から始まるループがある場合、頂点 v から始まる接続コンポーネント内の頂点の隣接頂点が v であることを意味し、検索プロセス中に頂点 v が必ず再び発生します。

実装のアイデア:

検索された各頂点をマークする
マークされた頂点に遭遇した場合、グラフ内にすでにサイクルが存在することを意味します。
グラフは無向グラフであるため、vw が連結されている場合、頂点 v の隣接リストには w が含まれ、w の隣接リストにも v が含まれますが、それらはサイクルを形成しないため、この状況を除外する必要があります。

パブリッククラスCycle{
    プライベートブール値 marked[];
    プライベートブールハッシュサイクル; 
 
パブリックCycle(グラフ グラフ) {
        this.marked = 新しいブール値[graph.V()];
 ( int s = 0; s < graph.V(); s++)の場合{
            if (!this.marked[s]) {
                dfs(グラフ, s, s);
            }
        }
    } 
 
    プライベートvoid dfs(グラフグラフ、 int v、 int pV) {
        this.marked[v] = true ;
 ( int w : graph.adj(v))の場合{
            if (!this.marked[w]) {
                this.dfs(グラフ、w、v);
            }そうでない場合 (w != pV) {
                this.hashCycle = true ;
戻る;
            }
        }
    } 
 
パブリックブールhasCycle() {
ハッシュサイクルを返します。
    }
 }

メソッド dfs のパラメーター v は検索する頂点を表し、pV は v に到達する頂点を表します。したがって、v の隣接リストにマークされた頂点があり、この頂点が v に到達する頂点と等しくない場合、グラフにサイクルが存在します。

無向グラフが二部グラフであるかどうかを確認する

二部グラフとは何ですか? グラフ内の各辺は、以下に示すように、異なる部分に属する頂点を接続します。

赤いノードは 1 つのセットを表し、白いノードは別のセットを表し、各エッジで接続された 2 つの頂点は異なるセットに属します。

実際の例で理解するのは簡単です。映画と俳優の関係。映画は頂点であり、俳優は頂点です。映画と俳優の間には直接のエッジはなく、俳優の間にも直接のエッジはありません。これは二部グラフです。

パブリッククラスTwoColorGraph {
    プライベートブール値 twoColor = true ;
    プライベートブール値[]がマークされています。
    プライベートブール値[] color; 
 
パブリックTwoColorGraph(グラフグラフ) {
        this.marked = 新しいブール値[graph.V()];
        this.color = 新しいブール値[graph.V()]; 
 
 ( int v = 0; v < graph.V(); v++)の場合{
            if (!this.marked[v]) {
                dfs(グラフ, v);
            }
        }
    } 
 
    プライベートvoid dfs(グラフグラフ、 int v) {
        this.marked[v] = true ;
 ( int w : graph.adj(v))の場合{
            if (!this.marked[w]) {
                this.color[w] = !this.color[v];
                dfs(グラフ, w);
            }そうでなければ（this.color[w] == this.color[v]）{
                this.twoColor = false ;
戻る;
            }
        }
    } 
 
パブリックブール値isTwoColor() {
 twoColorを返します。
    }
 }