深さ優先探索 【DFS】 Depth-First Search / 縦型探索

概要

深さ優先探索（DFS）とは、グラフや木構造を探索するためのアルゴリズムの一つで、それ以上先に進めない行き止まりのノードに出くわすまで経路を戻らずに隣接ノードを進んでいく方式。

グラフや木はあるノードから複数のノードへ経路が伸びている場合があり、すべてのノードを探索したい場合にどのような順番で辿っていくかについていくつかの戦略が考えられる。

深さ優先探索は探索を開始する頂点からの距離（深さ）が離れるように進んでいく方式で、それ以上進めない末端（木の場合は葉ノード、グラフの場合はすべての隣接ノードが探索済みの場合も含む）まで来たら、経路を遡って最初の未探索ノードへ進む。その先で末端に到達したら、再び経路を遡り…という手順を終了まで繰り返す。

最後（最も最近）に追加された候補を優先的に探索するLIFO（Last-In First-Out）方式で次に進むノードを決定するため、探索候補ノードの記録にはスタック（stack）というデータ構造が適している。関数の再帰呼び出しを用いると非常に簡潔にプログラムを記述できる。

もう一つの有力なアルゴリズムとして、頂点からの距離が同じノードを順番に訪ねていく方式があり、「幅優先探索」（BFS：Breadth-First Search）と呼ばれる。