深さ優先探索とは? わかりやすく解説

深さ優先探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2018/02/13 08:17 UTC 版)

深さ優先探索(ふかさゆうせんたんさく、: depth-first search, DFS、バックトラック法ともいう)は、グラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。






「深さ優先探索」の続きの解説一覧

深さ優先探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/29 13:54 UTC 版)

優先探索ともいう。根からできるだけ遠く、しかも、既に調べたノードの子であるノードから調べていく方法である。一般グラフ異なりこれまでに訪れたノード全て記憶しておく必要はないというのも木に閉路がないからである行きがけ順、通りがけ順、帰りがけ順探索はすべてこれの特殊な例である。

※この「深さ優先探索」の解説は、「二分木」の解説の一部です。» 「二分木」の概要を見る


深さ優先探索

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/07/14 05:46 UTC 版)

深さ優先探索は、現在のノード調査しその子ノードに対して同じことを繰り返す従って、再帰呼び出し容易に表現できるループでも実装可能)。走査法は、ノード調査する順序によって以下の3つ分類されるいずれの方法も、根から探索開始する)。 前順・先行順・前置順・行きがけ順 (英: pre-order) 根ノード調査するもしあれば左の部分木を前順走査するもしあれば、右の部分木を前順走査する2分探索木コピー作る際によく利用されるまた、数式構文木からポーランド記法表現を得るのにも利用される間順・中間順・通りがけ順 (英: in-order) もしあれば左の部分木を間順走査する根ノード調査するもしあれば、右の部分木を間順走査する多分木では定義されない2分探索木では、間順走査によって走査する順がソートされた順序になるため、よく使われる後順・後行順・後置順・帰りがけ順 (英: post-order) もしあれば左の部分木を後順走査するもしあれば、右の部分木を後順走査する根ノード調査する

※この「深さ優先探索」の解説は、「木構造 (データ構造)」の解説の一部です。» 「木構造 (データ構造)」の概要を見る

ウィキペディア小見出し辞書はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ

「深さ優先探索」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

深さ優先探索のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



深さ優先探索のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの深さ優先探索 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの二分木 (改訂履歴)、木構造 (データ構造) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2022 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2022 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2022 GRAS Group, Inc.RSS