Depth-First Search
Depth-First Search (深さ優先検索).
(Reference："Introduction to Algorithms, Second Edition")
可能ならば常に"より深く"、グラフを探索する。
未探索の edge(辺) が残されている vertex(頂点) の中で、最後に発見した頂点vのedgeを探索。vのedge全て全てを探索し終えると、vを発見したときに通ったedgeを "Back track(後戻り)"し、直前のvertexから出る edgeを再探索する。
DFS(G) for each vertex u ∈ V[G] do color[u] ← WHITE π[u] ← NIL time ← 0 for each vertex u ∈ V[G] do if color[u]= WHITE then DFS-Visit(u) DFS-Visit(u) color[u] ← GRAY time ← time +1 d[u] ← time for each vetex v ∈ Adj[u] do if color[v] = WHITE THEN π[v] ← u DFS-Visit(v) color[u] ← BLACK f[u] ← time ← time+1
表記：
Adj[u]:vertex uの隣接 vertexリスト
π[u] :predecessor vertex (uの先行vertex)
d[u]: vertex uを発見した時刻
f[u]: vertex uの隣接リストAdj[u]を調べ終えた時刻
time: 1 から 2|Vertex数|の、整数
[color]
WHITE:発見前のvertex
GRAY :発見後の全処理終了前の
BLACK:隣接リスト Adj[u]を調べ終えた時刻
Depth-First Search DFS の計算量は、Θ(|V| + |E|)
[Reference]:
Introduction to Algorithms, Second Edition
数学的基礎とデータ構造 (アルゴリズムイントロダクション)
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)
アルゴリズムイントロダクション 第3巻 精選トピックス
