プログラミングやアルゴリズムを学ぶうえで、「深さ優先探索（DFS）」は必ず習得すべき基本的なグラフ・木構造の探索アルゴリズムです。
「深さ優先探索ってどういう仕組み？」「スタックや再帰処理との関係は？」と疑問に思っている方のために、本記事では深さ優先探索の概念・アルゴリズム・実装方法をわかりやすく解説していきます。
グラフ探索の基礎を確実に理解することで、競技プログラミングや実際のシステム開発にも活用できる知識が身につきます。
深さ優先探索（DFS）とはグラフを縦方向に深く掘り進む探索アルゴリズムである
それではまず、深さ優先探索の基本的な定義と概念について解説していきます。
深さ優先探索（DFS：Depth-First Search）とは、グラフや木構造を探索する際に、一つの経路を行けるところまで深く進み、行き詰まったら戻って別の経路を探索するという戦略を持つアルゴリズムです。
名前の通り「深さ（Depth）」を優先する探索方法であり、縦方向への掘り下げを重視する点が特徴です。
迷路を解く際に「一つの通路をとことん進んで行き詰まったら引き返す」という方法をイメージすると理解しやすいでしょう。
深さ優先探索はスタック（Stack）または再帰処理（Recursive）によって実装できます。
再帰処理を使った実装は非常にコンパクトで可読性が高く、競技プログラミングでも頻繁に使われます。
深さ優先探索の仕組みと探索手順
続いては、深さ優先探索の具体的な仕組みと探索手順を確認していきます。
グラフと木構造の基礎知識
深さ優先探索を理解するうえで、まずグラフと木構造の基礎を押さえておきましょう。
グラフとは、ノード（頂点）とエッジ（辺）で構成されたデータ構造であり、有向グラフと無向グラフの2種類があります。
木構造はグラフの一種であり、ループ（閉路）を持たない連結グラフです。
深さ優先探索はどちらにも適用できますが、木構造への適用が最もシンプルで理解しやすいでしょう。
DFSの探索手順
1. 開始ノードをスタックに積む（または再帰関数の引数として渡す）
2. スタックのトップ（最後に積んだノード）を取り出す
3. 取り出したノードが未訪問であれば訪問済みにマークする
4. 取り出したノードに隣接する未訪問のノードをスタックに積む
5. スタックが空になるまで2〜4を繰り返す
この手順により、スタートノードから到達可能なすべてのノードを探索できます。
スタックを使ったDFSの動作例
具体的な例として、A→B→D、A→C→Eというエッジを持つ木構造をAから深さ優先探索する場合の動作を見てみましょう。
初期状態：スタック = [A]
ステップ1：Aを取り出して訪問。B・Cをスタックに積む → スタック = [B, C]
ステップ2：Cを取り出して訪問。Eをスタックに積む → スタック = [B, E]
ステップ3：Eを取り出して訪問。隣接ノードなし → スタック = [B]
ステップ4：Bを取り出して訪問。Dをスタックに積む → スタック = [D]
ステップ5：Dを取り出して訪問。隣接ノードなし → スタック = []
探索順序：A → C → E → B → D
スタックはLIFO（後入れ先出し）構造のため、最後に積んだノードが最初に取り出されます。
この特性が「深く進む」動作を実現しています。
深さ優先探索の実装方法
続いては、深さ優先探索の主要な実装方法を確認していきます。
再帰処理によるDFS実装（Python）
def dfs(graph, node, visited):
if node not in visited:
visited.add(node)
print(node)
for neighbor in graph[node]:
dfs(graph, neighbor, visited)
再帰処理を使うことで、コールスタックが自動的にスタックの役割を果たします。
スタックを使った反復DFS実装（Python）
def dfs_iterative(graph, start):
visited = set()
stack = [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
print(node)
stack.extend(graph[node])
反復処理による実装は、深いグラフでのスタックオーバーフローを防ぐことができます。
DFSの時間計算量と空間計算量
| 計算量の種類 | DFSの値 | 説明 |
|---|---|---|
| 時間計算量 | O(V + E) | V：頂点数、E：辺数 |
| 空間計算量 | O(V) | 訪問済み管理とスタックのメモリ |
DFSの時間計算量はO(V + E)であり、すべての頂点とエッジを一度ずつ走査することから導かれます。
深さ優先探索の主な活用場面
続いては、深さ優先探索が実際にどのような場面で活用されるかを確認していきます。
パスの探索と経路検出
DFSはグラフ上のある頂点から別の頂点への経路が存在するかどうかを調べる「経路探索」に活用されます。
迷路の解法や、ネットワーク上の到達可能性チェックなどに応用されています。
トポロジカルソート
有向非巡回グラフ（DAG）においてノードの依存関係を整列させる「トポロジカルソート」にDFSが使われます。
タスクのスケジューリングやビルドシステムの依存解決などに活用されます。
閉路（サイクル）の検出
グラフに閉路（ループ）が存在するかどうかを検出するためにもDFSが利用されます。
訪問中フラグと訪問済みフラグを使い分けることで、有向グラフの閉路検出が効率的に実現できます。
まとめ
本記事では、深さ優先探索（DFS）の仕組み・探索手順・実装方法・活用場面について解説しました。
DFSはグラフや木構造を深く掘り進む探索アルゴリズムであり、スタックまたは再帰処理によって実装できます。
時間計算量O(V + E)という効率的な計算量を持ち、経路探索・トポロジカルソート・閉路検出など幅広い場面で活用されます。
深さ優先探索と幅優先探索（BFS）の特徴を理解して使い分けることで、より高度なアルゴリズム設計が可能になるでしょう。
