深さ優先探索

深さ優先探索（DFS）は一つの分岐を最後までたどり、呼び出し元へ戻って次の分岐を試す。戻る経路をスタックに保持し、再帰呼び出しのスタックを使うのが自然な実装になる。隣接リストでは、到達可能な頂点と辺を O(V + E) 時間で探索できる。閉路検出、トポロジカルソート、連結性の解析の基礎となる。

迷路で道順を記録するように、分岐では一つの通路を選び、行き止まりなら前の分岐点へ戻る。この戻りがバックトラックであり、下降と同じく DFS の一部だ。

深さ優先探索の仕組み

ノードに入ったら訪問済みとして記録する。隣接ノードを順に調べ、未訪問なら再帰し、ループが終われば戻る。全ての下降に対応する復帰がある。スタックの最上段は現在のノードで、その下には子呼び出しの終了を待つ祖先が並ぶ。

本レッスンは二つのモードを持ち、コードも切り替わる。

• 木モード： 根から各ノードへの経路は一つだけ。子への辺をたどれば再訪しないため、コードは記録、再帰、復帰だけで、visited 集合を持たない。
• グラフモード： 辺が合流したり閉路を作ったりする。入口で visited を付け、未訪問の隣接ノードだけへ再帰する。訪問済みの対象がまだ呼び出しスタック上なら、祖先へ向かう後退辺であり、有向閉路を示す。既定例で終了済みノードへ向かう二辺は交差辺で、どちらもたどらない。一般の有向グラフでは終了済みの子孫へ向かう前進辺もあるため、終了済みの対象を全て交差辺と呼ぶことはできない。

深さ優先探索のステップ

既定はグラフモードの閉路ありプリセットで、0 から始める。六頂点の隣接リストは 0 → [1, 3]、1 → [2]、2 → [0, 4]、3 → [4, 5]、4 → [5]、5 → [1]。

1. dfs(0) で一番目の頂点を記録する。スタック [0] から 1 へ再帰する。
2. dfs(1) で二番目を記録する。スタック [0, 1] から 2 へ進む。
3. dfs(2) で三番目を記録する。スタックは [0, 1, 2]。2 → 0 はスタック上の祖先へ向かう後退辺なのでスキップし、4 へ再帰する。
4. dfs(4) で四番目を記録する。スタック [0, 1, 2, 4] から 5 へ進む。
5. dfs(5) で五番目を記録する。[0, 1, 2, 4, 5] が最大の深さになる。5 → 1 も後退辺なのでスキップする。その後 5 → 4 → 2 → 1 → 0 と戻る。
6. 0 のループに戻り、未訪問の 3 へ再帰する。六番目の頂点で、スタックは [0, 3]。3 → 4 と 3 → 5 の対象は終了済みで、この例では交差辺になる。両方をスキップし、3、0 の順に戻って終了する。

訪問順は 0、1、2、4、5、3。四辺は検査するが再帰ではたどらない。後退辺 2 → 0 と 5 → 1 は閉路を閉じ、交差辺 3 → 4 と 3 → 5 は終了済み領域へ重複して到達する。「スタック上にある」と「終了した」の区別が、この有向閉路検出の仕組みになる。

他のプリセットは訪問順だけを観察しやすい。木モードには平衡木と偏った木がある。七頂点の平衡木 0 → [1, 2]、1 → [3, 4]、2 → [5, 6] の DFS 順は 0, 1, 3, 4, 2, 5, 6。1 の部分木を終えてから兄弟 2 に進む。BFS は層ごとに 0, 1, 2, 3, 4, 5, 6 と訪問する。グラフの単純プリセットには交差辺が一つあり、後退辺はないので、訪問済み判定の役割を切り分けて見られる。

画面のフォーカスリングは呼び出しで辺を下り、復帰で上る。右側のスタックも一フレームずつ増減する。未訪問は薄青、スタック上はオレンジ、終了済みは緑。現在の呼び出しを濃く、待機中の祖先を薄く示す。後退辺や交差辺を拒否した瞬間、その辺が赤く光る。

時間計算量と空間計算量

訪問済みの印によって各到達可能頂点に一度だけ入り、有向辺は始点から一度検査する。再帰スタックは根から現在地までの経路を持ち、長い鎖では O(V) になる。訪問記録を含めても空間は O(V)。長い鎖では DFS のスタックが深くなり、BFS のキューは小さく保てる。一方、幅の広い層は BFS のキューを大きくする。

境界ケース

• 一頂点で辺がなければ、記録後にすぐ戻る。
• 非連結グラフでは、一回の DFS は始点から到達できる部分だけを訪問する。無向グラフなら始点の連結成分に当たる。全体を覆うには、未訪問頂点から再開する。
• 閉路があっても、訪問済み判定が実行中の呼び出しへの再入を防ぐ。
• 深い鎖では実行環境の再帰上限を超えることがある。明示的なスタックに置き換えられる。

よくある間違い

1. グラフで訪問済み判定を省く。閉路があると再帰が終わらない。省けるのは子への辺をたどる木モードだ。
2. 隣接ノードの処理後に印を付ける。実行中に閉路から再入できてしまうため、入口で印を付ける。
3. 下降だけを見て復帰を忘れる。トポロジカルソート、終了時刻、関節点などは戻る段階でも情報を処理する。
4. 正しい順番は一つだと思う。0 → [1, 2] と 0 → [2, 1] は異なるが、どちらも正しい DFS 順になる。
5. スタックとキューを混同する。DFS は後入れ先出しで深さを進み、BFS は先入れ先出しで層を進む。明示的なスタックでも、対応する訪問記録と隣接ノードの処理規則を保つ必要がある。