深さ優先探索

深さ優先探索（DFS）とは

深さ優先探索（Depth-First Search, DFS）は、グラフや木構造を探索するための基本的なアルゴリズムの一つです。このアルゴリズムは、スタート地点（根ノード）から可能な限り深く探索を進め、行き詰まったら一つ前のノードに戻る（バックトラック）という動作を繰り返します。この探索方法は、まるで迷路を壁伝いに進むようなイメージで、別名「縦型探索」とも呼ばれます。

深さ優先探索の概要

深さ優先探索は、以下のステップで実行されます。

1. 開始ノードの決定: 探索を開始するノード（根）を決定します。グラフの場合は、任意のノードを根とすることができます。
2. 探索の開始: 決定した開始ノードから、隣接する未探索のノードへと深く進みます。
3. 行き詰まりの処理: 探索が進めなくなる（隣接する未探索のノードがない）と、一つ前のノードに戻り、別の未探索のノードを探索します。
4. 探索の終了: すべてのノードを探索し終えるか、目的のノードを発見したら探索を終了します。

深さ優先探索の実装には、再帰を用いる方法と、スタックを用いる方法があります。再帰を用いる方法は、コードが簡潔になる一方で、スタックオーバーフローのリスクがあります。一方、スタックを用いる方法は、スタックオーバーフローのリスクを回避できますが、コードが少し複雑になります。

深さ優先探索の擬似コード

以下は、深さ優先探索の擬似コードです。

再帰ありの実装


function 深さ優先[探索]
v を訪問済みにする
v を処理する
for each v に接続しているノード i do
if i が未訪問 then
深さ優先[探索]


再帰なしの実装


function 深さ優先[探索]
S ← 空のスタック
v を訪問済みにする
v を S に積む
while S が空ではない do
v ← S から取り出す
v を処理する
for each v に接続しているノード i do
if i が未訪問 then
i を訪問済みにする
i を S に積む

深さ優先探索の利点と欠点

利点

省スペース: 一般的に、幅優先探索に比べて使用するメモリ量が少なくて済みます。特に、深い木構造やグラフにおいて、効率的な探索が可能です。
ヒューリスティックとの相性: 探索の分岐を選択する際に、ヒューリスティックな方法を適用しやすい場合があります。
実装の容易さ: 再帰的な実装は、コードが比較的簡単に書けます。

欠点

最適解の保証がない: 必ずしも最短経路を求めることができるわけではありません。迷路の出口を探索する場合、最短距離で出口にたどり着けるとは限りません。
無限ループのリスク: グラフに閉路が含まれる場合、探索が無限ループに陥る可能性があります。そのため、訪問済みのノードを記録する必要があります。

深さ優先探索の応用例

深さ優先探索は、様々な分野で応用されています。

迷路の探索: 迷路の解法を求めるアルゴリズムとして利用できます。
グラフの連結成分の検出: グラフがいくつかの連結成分に分かれている場合、それぞれの連結成分を検出できます。
トポロジカルソート: 有向グラフにおけるトポロジカルソート（ノード間の依存関係に基づく順序付け）に利用できます。
ゲームAI: ゲームの状況を探索し、最適な行動を選択するアルゴリズムとして利用できます。

幅優先探索との比較

深さ優先探索と対比されるアルゴリズムとして、幅優先探索（Breadth-First Search, BFS）があります。幅優先探索は、開始ノードに近いノードから順に探索を進めていくのに対し、深さ優先探索はより深く探索を進めていく点が異なります。一般的に、幅優先探索は最短経路を求めるのに適しており、深さ優先探索はより少ないメモリで探索を進めたい場合に適しています。

反復深化深さ優先探索

反復深化深さ優先探索（Iterative Deepening Depth-First Search, IDDFS）は、深さ優先探索の欠点である最適解の保証がないという点を補うための手法です。IDDFSは、深さ制限探索を段階的に深めていくことで、幅優先探索と同じく最短経路を求めることができます。これにより、深さ優先探索の省メモリ性と、幅優先探索の最適解保証という両方のメリットを享受できます。

まとめ

深さ優先探索は、木やグラフの探索に幅広く用いられる基本的なアルゴリズムです。再帰やスタックを利用して実装でき、省メモリで効率的な探索が可能です。ただし、最適解を保証しない場合もあるため、状況に応じて適切なアルゴリズムを選択する必要があります。

関連項目

深さ制限探索
* 幅優先探索

もう一度検索