アルゴリズムクイックリファレンス 第2版

6.2

 深さ優先探索

■

159

フの

深さ優先探索

の唯一の要件は、与えられた節点の隣接節点を反復処理する手段

があるということだけだ。この機能があれば複雑な情報の

深さ優先探索

を容易に行

うことができる。というのも、

dfsVisit

は、元のグラフの構造を読み込むだけだか

らだ。

6.2.3

 解

例6-1に

C

++

による解の例を示す。節点の色情報が、メソッド

dfsVisit

の内部で

しか使われないことに注意する。

例

6-1

 深さ優先探索の実装

//

グラフの節点

u

を訪問し情報を更新する

void dfsVisit (Graph const &graph, int u, /*

入力

*/

vector<int> &pred, vector<vertexColor> &color) { /*

出力

*/

color[u] = Gray;

// u

の全隣接点を処理する

for (VertexList::const_iterator ci = graph.begin(u);

ci != graph.end(u); ++ci) {

int v = ci->first;

//

未訪問節点を直ちに探索して

pred[]

を記録する

//

再帰呼び出しが終わると、隣接節点に後戻りする。

if (color[v] == White) {

pred[v] = u;

dfsVisit (graph, v, pred, color);

}

}

color[u] = Black; //

隣接点は既に終わり、この節点も終わった