深さ優先探索（DFS）
1本の道をできるだけ深くたどり、進めなくなると最後の分かれ道まで戻ってグラフを調べます。画面のスタックがその道です。
- 時間 O(V + E)
- メモリ O(V)
- スタックを使う
用語の意味
- 頂点: グラフの点。ここでは文字の入った円で描いています。
- 辺: 2つの頂点を結ぶ線。ここではどちら向きにもたどれます。
- 隣の頂点: ある頂点と辺で結ばれた頂点。アルファベット順に調べます。
- キュー: 先に入れたものが先に出ます。BFS はいつも一番長く待っている頂点を取り出します。
- スタック: 最後に入れたものが先に出ます。DFS はいつも最後にたどり着いた頂点から先へ進みます。
- V と E: 頂点の数と辺の数。O(V + E) は、どの頂点もどの辺も決まった回数だけ処理されるという意味です。
0 / 60 ステップ
- スタックの中
- 現在
- 完了
- 探索木の辺
- 飛ばした辺
A から始めます。再生を押すか、1ステップずつ進めてください。
スペースキー: 再生・一時停止。左右の矢印キー: ステップ移動。Home キーと End キー: ジャンプ。
試してみましょう: サイクルのあるグラフを選んでください。破線の辺はどれも、スタックにある頂点か完了した頂点へ戻る辺です。その辺がサイクルを閉じます。
仕組み
DFS は、まだ見ていない最初の隣の頂点で自分自身を呼び出し、次にその頂点の最初の新しい隣の頂点で呼び出す、と続けます。新しい隣の頂点がなくなると、その呼び出しは終わり、DFS は1つ前に戻って、そこで次の隣の頂点を試します。まだ終わっていない呼び出しはスタックになり、それはいつも始点から今の頂点までの道です。頂点の横の数字は、訪問した順番です。
向いている場面
そもそもどこまでたどり着けるかを調べる、サイクルを見つける、迷路を歩く、互いに依存する作業を順番に並べる、といったときに DFS を使います。最短の道は見つけません。