アルゴリズム・データ構造図鑑 · 入門

深さ優先探索:戻る場所を記録して奥へ進む

再帰や明示的スタックで探索し、訪問済みと探索中を区別する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 進める間は一つの枝をたどる
  2. 行き止まりから戻る例
  3. 有向グラフの閉路を見分ける
  4. 計算量と深い再帰
  5. この記事をロゲイアに質問する理解を確かめる

進める間は一つの枝をたどる

深さ優先探索(DFS)は、今の頂点から未発見の隣へ進み、さらにその先を探索します。進めなくなったら、以前の分岐へ戻って残る隣を調べます。この戻り先を再帰呼び出しのスタックや明示的なスタックで保持します。探索木の形や訪問順は隣接頂点の順番に依存しますが、訪問済み管理を正しく行えば、始点から到達できる頂点を調べられます。最短の辺数の順に訪ねる保証はありません。

行き止まりから戻る例

辺A→B、A→C、B→Dを考え、AではBを先に選びます。探索はA、B、Dと進み、Dの先に未発見頂点がないのでBへ戻り、Bの探索も終わるとAへ戻ります。そこで残るCへ進みます。訪問時に処理するのが行きがけ、全ての子の探索が終わってから処理するのが帰りがけです。経路の探索や依存関係の順序付けなど、どの時点の情報が必要かによって使い分けます。

有向グラフの閉路を見分ける

有向グラフで閉路を検出する場合、「未発見」「探索中」「探索完了」の状態を区別する方法があります。探索中の祖先へ戻る辺があれば閉路です。しかし既に探索完了した頂点へ向かう辺があるだけでは、閉路とは限りません。たとえばA→B、A→C、C→Bは閉路を持ちません。単なる訪問済みフラグだけで、訪問済み頂点への辺をすべて閉路扱いすると誤判定します。無向グラフでは親へ戻る辺の扱いも別に必要です。

計算量と深い再帰

隣接リスト表現で各頂点を一度発見し各辺を一定回数調べるDFSは、全体でO(V+E)です。訪問状態やスタックにはO(V)の補助領域を使います。細長いグラフでは再帰の深さが頂点数に比例するため、言語の再帰上限やスタック容量に注意します。明示的スタックへ置き換える際も、頂点を積むだけでよい用途と、再帰から戻る時点まで再現する必要がある用途を区別します。トポロジカル順序にはDAGという前提も必要です。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 11

学習コースから次を選ぶ