幅優先探索と深さ優先探索の違い：訪れる順・データ構造・最短経路・メモリ・用途を比較
どちらも、グラフや木の頂点を、辺をたどって漏れなく訪れる探索の方法です。幅優先探索(BFS)は、出発点から辺1本で行ける頂点をすべて訪れてから、2本で行ける頂点へ、というように近い順に広がっていきます。深さ優先探索(DFS)は、1本の道を行けるところまで進み、行き止まりになったら戻って別の道を進みます。幅優先探索はキュー、深さ優先探索はスタックか再帰で実装し、隣接リストで表したグラフなら、どちらも頂点の数と辺の数の和に比例する手間で全体を訪れます。辺に重みのないグラフの最短経路を求めるなら幅優先探索、すべての道を調べ尽くす処理や閉路の検出なら深さ優先探索がよく使われます。
| 項目 | 幅優先探索(BFS) | 深さ優先探索(DFS) |
|---|---|---|
| 訪れる順 | 出発点から近い順(たどる辺の数が少ない順)に、層ごとに広がる | 1本の道を奥まで進み、行き止まりになったら戻って、次の道へ進む |
| 使うデータ構造 | キュー(先入れ先出し) | スタック(後入れ先出し)、または再帰の呼び出し |
| 最短経路 | 辺に重みのないグラフでは、最初に到達したときの辺の数が、出発点からの最短になる | 最短は保証されない。遠回りの経路で先に到達することがある |
| 計算量(頂点の数 V、辺の数 E) | 隣接リストでは O(V + E)、隣接行列では O(V²) | 幅優先探索と同じく、隣接リストでは O(V + E)、隣接行列では O(V²) |
| 使うメモリ | 次に訪れる頂点をキューに覚えておく。枝分かれが多いと、1つの層の頂点がまとめてキューに入り、大きくなる | 再帰で書くと、今たどっている道の上の頂点を覚えておけばよく、道の深さに比例する。深すぎると、コールスタックがあふれることがある |
| 解が見つかるか | 頂点が有限なら、必ず見つかる。探索の範囲が際限なく広がる場合でも、浅い位置の解から順に見つかる | 有限のグラフで訪れた頂点を記録すれば、必ず見つかる。際限なく深くなる場合は、1本の道を進み続けて戻ってこないことがある |
| 木をたどる順 | レベル順(根から近い段ごとに、左から右へ) | 先行順(行きがけ順)、中間順(通りがけ順)、後行順(帰りがけ順) |
| 主な用途 | 重みのないグラフの最短経路、迷路の最短の手数、ネットワークで何段先まで届くかの計算 | 迷路やパズルの全通りの探索(バックトラック)、連結成分や閉路の検出、トポロジカルソート |
数値は代表的な目安で、世代や製品によって異なります。