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

概要

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

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

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

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

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

(2021.5.10更新)

他の辞典による解説 （外部サイト）

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。
ホーム画面への追加方法
1.ブラウザの 共有ボタンのアイコン 共有ボタンをタップ
2.メニューの「ホーム画面に追加」をタップ
閉じる