深さ優先探索とは？
深さ優先探索(DFS, Depth-First Search)は、一方向に行けるところまで深く進み、これ以上進めなければ戻って(バックトラッキング)別の道を探索するグラフ・木の走査法です。幅優先探索(BFS)と対をなす基本探索です。
核心の一行: 「まず一本の道を最後まで行ってみる」。 行き止まりに着いたら最も最近の分岐へ戻り、未訪問の道を試します。
スタックで動く
DFSの「戻る」はスタックで自然に表せます。最も一般的な実装は再帰で、このとき関数呼び出しスタックがその役割を担います。明示的なスタックを使いループで実装することもできます。
どちらでも訪問印(visited)が必須です。印がないと、サイクルのあるグラフで同じノードを無限に巡ります。
動作原理
ステップ1. 開始ノードに訪問印を付けます。
ステップ2. 隣接ノードのうちまだ訪れていない1つを選び、そちらへ深く進みます(再帰呼び出し)。
ステップ3. これ以上進めなければ呼び出しが終わり、前のノードへ戻ります。 そこでまた別の未訪問隣接を試します。
ステップ4. 到達可能な全ノードを訪れるまで繰り返します。
AlgoNoteの可視化は、深く進む辺と行き詰まって戻る瞬間を色で区別しステップごとに示します。
BFSとの違い
| DFS | BFS | |
|---|---|---|
| 構造 | スタック(再帰) | キュー |
| 順序 | 深さ優先 | 幅(近い)優先 |
| 向く問題 | 経路の有無・サイクル検出・トポロジカルソート・連結成分 | 重みなし最短経路・最小ステップ |
近い順に見るべき最短距離問題はBFS、「最後まで行って」構造を把握する問題はDFSが向きます。
時間計算量と空間計算量
| 計算量 | |
|---|---|
| 時間 | O(V + E) |
| 空間 | O(V) |
Vは頂点数、Eは辺数です。全頂点と辺を一度ずつ見るのでO(V + E)です。
例で追ってみる
辺 0 - 1、0 - 2、1 - 3 を持つグラフで0からDFS:
- •0訪問 → 1へ深く → 3へ深く → 3行き止まり、1へ戻る → 1行き止まり、0へ戻る → 2へ深く
- •訪問順の例: 0 → 1 → 3 → 2
よくあるミス
- •訪問印の欠落: サイクルで無限ループに陥ります。DFS最大の落とし穴です。
- •印のタイミング: ノードに入るとき印を付け、同じノードを2回キュー/スタックに入れないようにします。
- •再帰の深さ制限: 非常に深いグラフは呼び出しスタックが溢れ得るので、明示的スタックに変えることもあります。
AlgoNoteで直接確認しましょう
DFSが一本の道を深く進み、行き詰まると戻って別の道を試す過程をAlgoNoteでステップごとに確認できます。