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