深さ優先探索とは
ふかさゆうせんたんさく
グラフや木を、1本の道を行けるところまで進み、行き止まりになったら戻って別の道を進む順に訪れる探索の方法。再帰やスタックで実装し、迷路の探索、連結成分や閉路の検出、トポロジカルソートなどに使われる。英語の頭文字からDFSともいう。
「深さ優先探索」は、1分野の3問の練習問題に出てきます(データ構造とアルゴリズムなど)。
この用語の分野: データ構造とアルゴリズム
深さ優先探索の練習問題に挑戦
辺に向きのないグラフで、各頂点の隣の頂点が次のとおりである。A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E。頂点 A から再帰的な深さ優先探索を行う。隣の頂点はここに書いた順に調べ、まだ訪れていない頂点が見つかったらすぐにその頂点へ進む。頂点を訪れる順はどれか。
- AA, B, C, D, E, F
- BA, B, D, E, C, F
- CA, B, D, E, F, C
解説の中の「深さ優先探索」
A, B, D, E, C, F は、E から未訪問の F へ進まずに戻ってしまっており、深さ優先探索の順にはなりません。
辺に向きのないグラフで、各頂点の隣の頂点が次のとおりである。A: B, C / B: A, D, E / C: A, …深さ優先探索(再帰やスタックを使う)は1本の道を行けるところまで進むので、遠回りの経路で先に到達することがあり、最短は保証されません。
辺に重みのないグラフで、出発点から各頂点までの最短の辺の数を求めたい。適した探索の方法と、そのとき使うデータ構造の組は…トポロジカルソートは、向きがあって閉路のないグラフ(DAG)で、すべての辺が前から後ろへ向くように頂点を並べる操作で、入ってくる辺のない頂点から順に取り出す方法(カーンの方法)や深さ優先探索で求められます。
作業 A〜E に「A は C より前」「B は C より前」「C は D より前」「B は E より前」「E は D …
「深さ優先探索」が出てくる問題(3問)
- 辺に向きのないグラフで、各頂点の隣の頂点が次のとおりである。A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E。頂点 A から再帰的な深さ優先探索を行う。隣の頂点はここに書いた順に調べ、まだ訪れていない頂点が見つかったらすぐにその頂点へ進む。頂点を訪れる順はどれか。
- 辺に重みのないグラフで、出発点から各頂点までの最短の辺の数を求めたい。適した探索の方法と、そのとき使うデータ構造の組はどれか。
- 作業 A〜E に「A は C より前」「B は C より前」「C は D より前」「B は E より前」「E は D より前」という順序の制約がある。すべての制約を満たす作業の順(トポロジカルソートの結果)はどれか。
データ構造とアルゴリズムの参考書を探す PR
Amazonの検索結果へのリンクです。Amazonのアソシエイトとして、半導体教室は適格販売により収入を得ています。