深さ優先探索 (DFS)
迷路に入り、行き止まりまで進んだら、最後の分かれ道まで戻って次の道を試す。深さ優先探索はこれと同じやり方でグラフを探索します。最も単純なグラフアルゴリズムの一つですが、その使うスタックは思った以上に多くのことを教えてくれます。
考え方
グラフは、エッジでつながったノードの集まりです。部屋とドア、Web ページとリンク、タスクとそれが依存するタスクなどです。深さ優先探索はスタートから到達できるすべてのノードを訪問しますが、その順番に特徴があります。常に一番最近到達したノードから続けるのです。今いるノードをスタックに保持します。新しいノードは一番上に積まれ、ノードが降ろされるのは、周りをすべて探索し終えたときだけです。
ステップごとに
スタートをスタックに積み、訪問番号 1 を付けます。一番上のノードの、次の隣接ノードを見ます。まだ見ていなければ、次の訪問番号を付け、到達元のノードを記録して、スタックの一番上に積みます。見たことがあれば飛ばします。一番上のノードに調べる隣接ノードが残っていなければ、そのノードは完了です。降ろして、その下のノードで続けます。スタックが空になるか、ゴールに着いたら終わりです。
例
エッジ A–B、A–C、B–D、C–D、C–E、D–F を持つグラフで、A から始め、隣接ノードをアルファベット順に調べます。探索は A から B、B から D、D から C、C から E へと進むので、スタックは A, B, D, C, E です。途中で C は、まだスタックにある A を見ます。エッジ C–A が閉路 A, B, D, C を作ります。E には新しい隣接ノードがないので完了し、次に C も完了して、探索は D に戻ります。D にはまだ F があります。訪問順は A, B, D, C, E, F です。E をゴールにすると、DFS は経路 A → B → D → C → E (エッジ4本) で止まりますが、A → C → E ならエッジ2本で済みます。
何に役立つか
スタックは常にスタートから現在のノードまでの経路なので、DFS は迷路やパズルに自然に向いています。これがバックトラックの考え方です。向きのないグラフでは、まだスタックにあるノードへのエッジは閉路を作ります。向きのあるグラフでは、ノードを完了した順の逆に並べるとトポロジカル順序になり、各タスクがそれが依存するタスクの後に来ます。深さ優先探索は連結成分、橋、関節点も見つけられ、そのランダム版は迷路を生成する定番の方法です。
歴史
19世紀、フランスの数学者シャルル・ピエール・トレモー (Charles Pierre Trémaux) は、通路に印を付けてどんな迷路からも抜け出す方法を示しました。これはチョークで行う深さ優先探索です。1972年と1973年、ロバート・タージャン (Robert Tarjan) とジョン・ホップクロフト (John Hopcroft) は、強連結成分から、グラフを交差なしで描けるかどうかの判定まで、多くのグラフ問題を DFS で線形時間で解けることを示しました。二人はこの業績もあって1986年のチューリング賞を受賞しました。
試してみよう
アプリを開いて「ステップ」を押してください。隣接ノードを調べているノードが強調され、スタック内のノードは青、完了したノードは緑で、それぞれに訪問番号が付きます。スタックはグラフの下に、スタートから一番上のノードまで表示されます。閉路を作るエッジはステータス行で確かめ、ゴールを選んで、見つかった経路が幅優先探索と比べてどれほど長くなりうるかを見てみましょう。
よくある質問
DFS の時間計算量は?
V 個のノード (頂点) と E 本のエッジに対して O(V + E) です。各ノードはスタックに1回積まれて1回降ろされ、各エッジは両端から調べられます。スタックと印のために O(V) の追加メモリが必要です。
DFS はなぜスタックを使うのですか?
後入れ先出しにより、探索が一番新しいノードから続き、その一つ前のノードに戻れるからです。再帰はプログラムのコールスタックで同じことをします。代わりにキューを使うと、探索は輪を描くように広がります。それが幅優先探索です。
再帰による DFS は大きなグラフで問題になりますか?
なることがあります。長い経路は深い再帰を意味し、多くの言語は呼び出しの深さに制限があります。ループで明示的なスタックを使えば、同じ順番でノードを訪問しつつ、この制限を避けられます。
DFS はどこで使われますか?
バックトラックによる迷路やパズルの解法、閉路の検出、依存関係に沿ったタスクの順序付け (トポロジカルソート)、連結成分と強連結成分の検出、迷路の生成、依存グラフをたどるコンパイラやビルドツールなどです。
試してみますか?
ブラウザで PictorX を開きます。インストール不要、始めるのにクレジットカードも不要です。
深さ優先探索を試す