深さ優先探索と連結成分

深さ優先探索(Depth First Search)の主な考え方は、まず未訪問の頂点を開始頂点とし、現在の頂点の辺に沿って未訪問の頂点へ移動することです。未訪問の頂点がなくなった場合は、前の頂点に戻って他の頂点を試し続け、すべての頂点が訪問されるまで続けます。

下図の例では、0から開始した場合の走査順序は右図のようになります。

無向グラフ G の極大連結部分グラフは、G の連結成分(connected component)と呼ばれます。連結グラフは連結成分を1つだけ持ち、それは自身です。非連結の無向グラフは複数の連結成分を持ちます。連結成分と連結成分の間には辺は一切ありません。深さ優先探索を用いて連結成分を求めることができます。

以下では、連結成分を求めることを例にして、グラフの深さ優先探索を実装します。これを dfs と呼びます。以下のコード断片では、visited 配列は dfs の過程でノードが訪問されたかどうかを記録し、ccount は連結成分の数を記録し、id 配列は各ノードに対応する連結成分のラベルを表します。2つのノードが同じ id 値を持つ場合、同じ連結成分に属することを意味します。

...
// コンストラクタ、重みなしグラフの連結成分を求める
public Components(Graph graph){
    // アルゴリズムの初期化
    G = graph;
    visited = new boolean[G.V()];
    id = new int[G.V()];
    ccount = 0;
    for( int i = 0 ; i < G.V() ; i ++ ){
        visited[i] = false;
        id[i] = -1;
    }
    // グラフの連結成分を求める
    for( int i = 0 ; i < G.V() ; i ++ )
        if( !visited[i] ){
            dfs(i);
            ccount ++;
        }
}
...

グラフの深さ優先探索は再帰的な処理です。実装コードは次の通りです。

...
// グラフの深さ優先探索
void dfs( int v ){

    visited[v] = true;
    id[v] = ccount;

    for( int i: G.adj(v) ){
        if( !visited[i] )
            dfs(i);
    }
}
...

Java サンプルコード

ソースコードパッケージのダウンロード:Download

src/サンプル/graph/Components.java のコード:

package サンプル.graph;

import サンプル.graph.read.Graph;

/**
* 深さ優先探索
 */

public class Components {

    Graph G;                    // グラフの参照
    private boolean[] visited;  // dfs の過程でノードが訪問されたかどうかを記録する
    private int ccount;         // 連結成分の数を記録する
    private int[] id;           // 各ノードに対応する連結成分のラベル

    // グラフの深さ優先探索
    void dfs( int v ){

        visited[v] = true;
        id[v] = ccount;

        for( int i: G.adj(v) ){
            if( !visited[i] )
                dfs(i);
        }
    }

    // コンストラクタ、重みなしグラフの連結成分を求める
    public Components(Graph graph){

        // アルゴリズムの初期化
        G = graph;
        visited = new boolean[G.V()];
        id = new int[G.V()];
        ccount = 0;
        for( int i = 0 ; i < G.V() ; i ++ ){
            visited[i] = false;
            id[i] = -1;
        }

        // グラフの連結成分を求める
        for( int i = 0 ; i < G.V() ; i ++ )
            if( !visited[i] ){
                dfs(i);
                ccount ++;
            }
    }

    // グラフの連結成分の数を返す
    int count(){
        return ccount;
    }

    // 頂点vと頂点wが連結かどうかを調べる
    boolean isConnected( int v , int w ){
        assert v >= 0 && v < G.V();
        assert w >= 0 && w < G.V();
        return id[v] == id[w];
    }
}
その他の拡張