アルゴリズムを学ぶうえで、「深さ優先探索（DFS）」と「幅優先探索（BFS）」は必ずセットで理解すべき重要な概念です。
どちらもグラフや木構造を探索するアルゴリズムですが、探索の順序・メモリ使用量・適した用途が異なります。
「DFSとBFSの違いが今ひとつ理解できない」「どちらを使えばいいの？」という方のために、本記事では両アルゴリズムの特徴・違い・使い分けを徹底的に解説していきます。
DFSとBFSの最大の違いは探索順序とデータ構造にある
それではまず、DFSとBFSの最も根本的な違いについて解説していきます。
深さ優先探索（DFS）はスタック（または再帰処理）を使って縦方向（深さ方向）に優先して探索するアルゴリズムであり、幅優先探索（BFS）はキューを使って横方向（幅方向）に優先して探索するアルゴリズムです。
同じグラフを探索しても、DFSとBFSでは訪問するノードの順序が全く異なります。
DFSは「行けるところまで深く進んでから引き返す」戦略です。
BFSは「現在のノードから隣接するすべてのノードを先に訪問してから次の層へ進む」戦略です。
この探索戦略の違いが、適切な使い分けを決定する最大の要因になります。
DFSとBFSの仕組みを比較して理解する
続いては、DFSとBFSの仕組みの違いを具体的に比較して確認していきます。
使用するデータ構造の違い
DFSはスタック（LIFO：後入れ先出し）を使用します。
スタックの特性により、最後に追加したノードが最初に取り出されるため、より深いノードへの探索が優先されます。
BFSはキュー（FIFO：先入れ先出し）を使用します。
キューの特性により、最初に追加したノード（同じ深さのノード）が先に処理されるため、幅方向への均等な探索が実現されます。
具体的な探索順序の比較
以下のような木構造（ルートA、子B・C、Bの子D・E、Cの子F）を探索する場合：
DFSの探索順序（スタック使用）：A → B → D → E → C → F
BFSの探索順序（キュー使用）：A → B → C → D → E → F
DFSは深さ方向を優先し、BFSはルートに近いノードを先に訪問する点が明確に異なります。
メモリ使用量の違い
DFSのメモリ使用量はO(H)であり、Hは木の高さ（最大深さ）です。
BFSのメモリ使用量はO(W)であり、Wは木の最大幅（最も多くのノードを持つ層のノード数）です。
木の形状によってどちらがメモリ効率に優れるかが変わります。細長い木ではDFSが有利であり、幅広い木ではBFSがメモリを多く消費します。
DFSとBFSの計算量と性能比較
続いては、DFSとBFSの計算量と性能について比較確認していきます。
時間計算量の比較
| 比較項目 | DFS（深さ優先探索） | BFS（幅優先探索） |
|---|---|---|
| 使用データ構造 | スタック（または再帰） | キュー |
| 時間計算量 | O(V + E) | O(V + E) |
| 空間計算量 | O(H)（木の高さ） | O(W)（木の最大幅） |
| 最短経路の保証 | なし | あり（辺の重みが均一な場合） |
| 無限グラフへの適用 | 非推奨（無限ループの可能性） | 適用可能 |
時間計算量はDFS・BFSともにO(V + E)で同等ですが、空間計算量やアルゴリズムの特性に違いがあります。
最短経路の探索能力の違い
BFSは辺の重みが均一（すべての辺のコストが等しい）な場合に、スタートノードから各ノードへの最短経路を保証します。
これはBFSが層ごとに探索を進めるため、最初に到達したパスが最短パスと一致するためです。
DFSは最短経路の保証がないため、最短経路探索にはBFSが適しています。
DFSとBFSの使い分けと適した用途
続いては、DFSとBFSの適した用途と使い分けの基準を確認していきます。
DFSが適しているケース
DFSが特に力を発揮するのは以下のような場面です。
トポロジカルソートや閉路（サイクル）検出では、DFSの「深く潜る」特性が効果的に機能します。
迷路の全経路列挙や組み合わせの全探索（バックトラッキング）にもDFSが適しています。
連結成分の検出や木の直径・深さの計算にも頻繁に使われます。
メモリが限られた環境や、解が木の深部にある可能性が高い場合はDFSの方が効率的です。
BFSが適しているケース
BFSは最短経路を求める問題に最も適しています。
Webクローラーや友人関係ネットワークの「近い順」での探索にBFSが使われます。
ゲームにおける「最短手数での解法探索」（例：ルービックキューブ、15パズル）もBFSの典型的な活用例です。
幅広く浅い探索が必要な場面では、BFSが本来の強みを発揮します。
DFS・BFSの使い分けフローチャート
Q1. 最短経路・最短手数を求める必要がある？
→ Yes：BFSを選択
→ No：次の質問へ
Q2. 全経路列挙・バックトラッキングが必要？
→ Yes：DFSを選択
Q3. グラフが非常に幅広い（最大幅が大きい）？
→ Yes：DFSの方がメモリ効率が良い場合がある
→ No：用途に応じてどちらでも可
まとめ
本記事では、深さ優先探索（DFS）と幅優先探索（BFS）の違い・特徴・使い分けについて解説しました。
DFSはスタックを使って深さ方向に探索し、BFSはキューを使って幅方向に探索するという探索戦略の違いが最大のポイントです。
BFSは最短経路の保証があり、DFSはバックトラッキングや全経路探索に優れています。
問題の性質に応じてDFSとBFSを適切に選択することが、効率的なアルゴリズム設計の基本です。
両方のアルゴリズムを実装して動作を体感することで、理解がより深まるでしょう。
