読み方 ： ふかさゆうせんたんさく

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

概要

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

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

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

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

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

他の辞典等による「深さ優先探索」の解説 （外部サイト）

資格試験などの「深さ優先探索」の出題履歴

▼ 基本情報技術者試験
【令8修6】 図の木構造において，木の根の左の葉から行きがけ順深さ優先によって探索した場合，●の葉は何番目に探索されるか。ここで，木の根の探索は0番目とする。
この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。