アルゴリズムの学習で「BFSとDFSはわかったけど、どちらを使えばいいか判断できない」という悩みをお持ちの方も多いのではないでしょうか。
この記事では、幅優先探索と深さ優先探索の使い分けについて、それぞれの特徴と実際の応用例を豊富に解説しています。
BFSとDFSの適切な使い分けを習得することで、グラフ問題の解決力が大幅に向上するでしょう。ぜひ参考にしてください。
BFSとDFSの特徴を比較して使い分けの基準を理解しよう
それではまず、BFSとDFSの特徴比較と使い分けの基準について解説していきます。
使い分けの大原則：最短経路・近さの順番が重要な問題→BFS。深い探索・全パターン列挙・経路の有無確認が重要な問題→DFS。この判断基準を押さえておくと、多くの問題で迷わず選択できます。
| 使い分けの観点 | BFS（幅優先）が適する | DFS（深さ優先）が適する |
|---|---|---|
| 最短経路 | 重みなしグラフの最短経路を求める | 最短経路の保証は不要な場合 |
| 探索の深さ | 答えが比較的浅い場所にある | 答えが深い場所にある可能性がある |
| メモリ | 幅が狭いグラフ・メモリに余裕がある | 幅の広いグラフ・メモリを節約したい |
| 全探索 | レベル順の全探索 | 全経路の列挙・バックトラッキング |
BFSが適している問題と応用例
続いては、BFSが適している問題と応用例を確認していきます。
迷路の最短経路問題
迷路の最短経路（最小手数）を求める問題はBFSの典型的な応用例です。
BFSは起点から近い順に探索するため、ゴールに最初に到達したとき、その経路が最短経路であることが保証されます。
二次元グリッドの迷路をグラフとして表現し、上下左右の移動を隣接ノードへの移動として扱うことでBFSを適用できます。
SNSでの最短距離（友達の友達）
「AさんとCさんは何人介在すると繋がるか」というSNSの友人関係の最短距離もBFSで解ける問題です。
FacebookやLinkedInの「知り合いかも」機能の背景にはBFSに基づくグラフ探索が使われています。
Webクローラーのリンク探索
Webクローラー（検索エンジンのボット）がWebページのリンクをたどって収集する際にもBFSが使われます。
起点ページから近い（リンクが少ない）ページを先に収集するBFS方式は、重要なページを優先的に収集できる利点があります。
DFSが適している問題と応用例
続いては、DFSが適している問題と応用例を確認していきます。
迷路の全経路探索・バックトラッキング
迷路のすべての経路を列挙したい場合や、条件を満たす経路があるかどうかを探索する問題ではDFSが向いています。
DFSはバックトラッキング（行き止まりに達したら引き返す）と相性が良く、ナイツツアー問題・数独ソルバー・組み合わせの全列挙などに応用されます。
有向グラフの位相ソート
タスクの依存関係グラフを解析して実行順序を求める「位相ソート（Topological Sort）」はDFSで実装できます。
DFSでノードの探索が完了した順番を逆にすることで、位相ソートの順序が得られます。
連結成分の検出とサイクル検出
グラフが連結かどうかを判定したり、閉路（サイクル）が存在するかを検出したりする問題でもDFSがよく使われます。
木構造の全探索や、再帰を使ったアルゴリズムの実装でもDFSの考え方が基礎になっています。
BFSとDFSのどちらにも対応できる問題の考え方
続いては、BFSとDFSのどちらにも対応できる問題の考え方を確認していきます。
問題によってはBFSとDFSのどちらでも解けるものがあります。
グラフの連結確認はどちらでも可能
グラフのすべてのノードが連結しているかどうかの確認はBFSでもDFSでも実装できます。
選択の基準は実装のしやすさや、コードの可読性で判断しても構いません。
実務での選択基準まとめ
最短経路が必要→BFS、全探索・再帰処理・バックトラッキング→DFS、メモリが制約→DFS（スタックサイズの制限に注意）、実装の簡潔さ→DFS（再帰を使う場合）という基準で選択するとよいでしょう。
まとめ
この記事では、幅優先探索と深さ優先探索の使い分けについて、特徴の比較・BFS・DFSそれぞれの応用例まで詳しく解説しました。
最短経路・近さが重要な問題にはBFS、全探索・深い探索・バックトラッキングが必要な問題にはDFSという使い分けの基準を覚えておきましょう。
今回の内容を参考に、問題の性質を見極めてBFSとDFSを適切に使い分けていきましょう。
