深さ優先探索と連結成分
深さ優先探索(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 ++;
}
}
...
// コンストラクタ、重みなしグラフの連結成分を求める
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);
}
}
...
// グラフの深さ優先探索
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];
}
}
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];
}
}