markdown
DFS と BFS の基本
lecture/information/algorithm/search/DFSとBFSの基本-講義.n.md
DFS と BFS の基本
algorithmsearchundergraduatelecture
導入
この講義で最重要なのは、DFS と BFS を「別々の手法」でなく、どの順番で候補を取り出すかの違いとして見ることです。
探索でつまずきやすいのは、DFS と BFS の名前だけを覚えて、なぜ DFS は深く潜り、BFS は近い順に広がるのかが見えないことです。この講義では、スタックとキューの取り出し順からその違いを説明します。
用語と定義
DFS とは、現在地から行けるところをできるだけ深く進む探索です。
BFS とは、始点から距離の近い順に探索する方法です。
方針
まず DFS はスタック、BFS はキューと結びつけます。そのあと、それぞれの探索順がどんな情報を得やすいかを整理します。
直感的な説明
DFS は迷路で一本の道をどんどん進み、行き止まりで戻る動きです。BFS は波紋のように、始点から 1 歩、2 歩、3 歩 と外側へ広がります。
厳密な説明
1. DFS
スタックや再帰を使うと、最後に見つけた候補から先に処理します。だから、今いる場所から先へ進めるだけ進む探索になります。
2. BFS
キューを使うと、先に見つけた候補から順に処理します。だから、始点から距離 1 の点を全部見てから、距離 2 の点へ進みます。
3. 使いどころ
DFS は連結の確認や全探索と相性がよく、BFS は最短手数や最短距離を求める問題と相性がよいです。
見分け方
- 最短を問うなら、まず BFS を疑います。
- 全部たどる、戻りながら調べる、という流れなら DFS を疑います。
- スタックなら DFS、キューなら BFS という対応を意識すると整理しやすいです。
最終形
\boxed{\text{DFS = stack 的探索,\quad BFS = queue 的探索}}
一言でいうと
- DFS と BFS の違いは、探索対象の違いではなく、候補の取り出し順の違いです。