深さ優先探索
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/05/07 14:28 UTC 版)
深さ優先探索（ふかさゆうせんたんさく、英: depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。
- 1 深さ優先探索とは
- 2 深さ優先探索の概要
- 3 反復深化深さ優先探索
深さ優先探索
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/29 13:54 UTC 版)
奥優先探索ともいう。根からできるだけ遠く、しかも、既に調べたノードの子であるノードから調べていく方法である。一般のグラフと異なりこれまでに訪れたノードを全て記憶しておく必要はない。というのも木には閉路がないからである。行きがけ順、通りがけ順、帰りがけ順探索はすべてこれの特殊な例である。
※この「深さ優先探索」の解説は、「二分木」の解説の一部です。
「深さ優先探索」を含む「二分木」の記事については、「二分木」の概要を参照ください。
深さ優先探索
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/14 05:46 UTC 版)
「木構造 (データ構造)」の記事における「深さ優先探索」の解説
深さ優先探索は、現在のノードを調査し、その子ノードに対して同じことを繰り返す。従って、再帰呼び出しで容易に表現できる（ループでも実装可能）。走査法は、ノードを調査する順序によって以下の3つに分類される（いずれの方法も、根から探索を開始する）。 前順・先行順・前置順・行きがけ順 (英: pre-order) 根ノードを調査する。 もしあれば、左の部分木を前順走査する。 もしあれば、右の部分木を前順走査する。 2分探索木のコピーを作る際によく利用される。また、数式の構文木からポーランド記法の表現を得るのにも利用される。 間順・中間順・通りがけ順 (英: in-order) もしあれば、左の部分木を間順走査する。 根ノードを調査する。 もしあれば、右の部分木を間順走査する。 多分木では定義されない。2分探索木では、間順走査によって走査する順がソートされた順序になるため、よく使われる。 後順・後行順・後置順・帰りがけ順 (英: post-order) もしあれば、左の部分木を後順走査する。 もしあれば、右の部分木を後順走査する。 根ノードを調査する。
※この「深さ優先探索」の解説は、「木構造 (データ構造)」の解説の一部です。
「深さ優先探索」を含む「木構造 (データ構造)」の記事については、「木構造 (データ構造)」の概要を参照ください。
「深さ優先探索」の例文・使い方・用例・文例
- 深さ優先探索のページへのリンク
