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

160

■

6

章 グラフアルゴリズム

//

始点から探索を始める。

dfsVisit (graph, s, pred, color);

}

6.2.4

 分析

再帰関数

dfsVisit

は、グラフの各節点に対して一度だけ呼ばれる。

dfsVisit

の

中では、すべての隣接節点を調べねばならない。すなわち、有向グラフでは、辺は

いずれも一度たどられるだけだが、無向グラフでは、一度たどられた後に（逆方向

から）もう一度チェックされることになる。どちらも、全体の性能コストは、

O(V

＋

E)

となる。

6.2.5

 変形

元のグラフが非連結なら、

s

からの経路がない節点がいくつかあるだろう。これ

らの節点は未訪問のままになる。変形の中には、

dfsSearch

メソッド内で未訪問節

点に対して

dfsVisit

を追加実行し、すべての節点の処理を保証するものもある。こ

れが行われると、

pred[]

値は、深さ優先木探索結果の深さ優先森を記録する。この

森で木の根を見つけるには

、

pred[]

を走査して、

pred[r]

値が−

1

の節点

r

を見つ

けることになる。

6.3

 幅優先探索

幅優先探索

は、グラフ探索で

深さ優先探索

とは異なる方式を取る。

幅優先探索

では、

始点

s

から

k

辺だけ離れたグラフ

G

＝

(V, E)

のすべての節点を、

k

＋

1

辺だけ離れた

どの節点よりも先に訪問する。この処理は、

s

から到達可能な節点がなくなるまで続

けられる。

幅優先探索

では、

s

から到達不能な

G

の節点を訪問しない。アルゴリズム

は、有向グラフでも無向グラフでも機能する。

幅優先探索