1 歩ずつ動かす
- いま奥にいる頂点
- A
- 見ている辺
- なし
- 訪れた順
- A
いま通っている道 (下が開始の頂点、上がいちばん奥)
- A
戻った頂点
- いちばん奥にいる頂点
- 訪問済み (右上の数は訪れた順)
- まだの頂点
- いま見ている辺
隣が 2 つ以上あるときは、名前の順 (A、B、C…) に見ます。訪問済みにするのは、その頂点へ着いたときです。
1 歩目 / 全 21 歩見た辺 0 本訪問済み 1 個道の長さ 1
開始の頂点 A を訪問済みにして、道に積みます。隣は B、C です。名前の順に見ます。
いま動いている疑似コードの行
- 1visit(s) を呼ぶ (s は開始の頂点)
- 2visit(u) は、まず u を訪問済みにする
- 3u の隣 v を、名前の順に 1 つずつ見る
- 4まだの v は、visit(v) を呼んで奥へ進む
- 5訪問済みの v は、何もしない
- 6隣を全部見終えたら、呼び出し元へ戻る
見本を変える
予想してみる
いまは 1 歩目です。
次に訪問済みになるのは、どの頂点でしょう。
今回わかること
- 行き止まりまで奥へ進み、戻ってから別の隣へ行く流れ
- 再帰の呼び出し (道) が積み重なって戻る様子と、訪問済みの印が要る理由
前提
- スタック (最後に入れた物から出る)
- 再帰 (自分を呼ぶ関数)
- グラフの頂点と辺
どんなたどり方か
深さ優先探索 (DFS) は、開始の頂点から行ける所まで奥へ進み、行き止まりになったら一つ前へ戻って、別の隣を試すたどり方です。迷路で、分かれ道を一本ずつ奥まで確かめるのと同じです。
いま通っている道は、スタックと同じ形で積み重なります。最後に進んだ頂点から先に戻るので、再帰の呼び出しでそのまま書けます。一度訪れた頂点に印を付けておくと、輪のあるグラフでも同じ頂点を何度も調べません。
手順と具体例
- 1開始の頂点を訪問済みにして、道に積む
- 2いちばん奥の頂点の隣を、名前の順に 1 つ見る
- 3まだの隣があれば、訪問済みにして道に積み、2 に戻る
- 4隣を全部見終えたら、道から外して 1 つ手前へ戻る
- 5道が空になるまで、2 から 4 をくり返す
| 動き | 道 (下から) | 訪れた順 |
|---|---|---|
| A から始める | A | A |
| A から B へ進む | A、B | A B |
| B から D へ進む | A、B、D | A B D |
| D から戻る | A、B | A B D |
| B から E へ進む | A、B、E | A B D E |
| E から戻る | A、B | A B D E |
| B から戻る | A | A B D E |
| A から C へ進む | A、C | A B D E C |
| C から F へ進む | A、C、F | A B D E C F |
| F から戻る | A、C | A B D E C F |
| C から G へ進む | A、C、G | A B D E C F G |
| G から戻る | A、C | A B D E C F G |
| C から戻る | A | A B D E C F G |
| A から戻る | 空 | A B D E C F G |
見る回数と計算量
| 数えるもの | 回数 | 計算量 |
|---|---|---|
| 訪問済みにして道に積む | 頂点 1 個につき 1 回 | O(V) |
| 辺を見る | 辺 1 本につき 2 回 (両側から) | O(E) |
| 合わせて | 頂点の数と辺の数の和に比例 | O(V + E) |
V は頂点の数、E は辺の数です。木の見本は頂点 7 個、辺 6 本なので、積むのが 7 回、辺を見るのが 12 回です。幅優先探索と回数は同じで、違うのは訪れる順だけです。道の長さは最大で V になるので、とても深いグラフを再帰で書くと、言語の呼び出しの深さの上限に当たることがあります。隣を名前の順に並べ替える手間は、図を追いやすくするための物で、ここでは数えていません。
使いどころ
向いているとき
- 行ける所を全部調べたいとき (つながっている塊の数え上げ)
- ある道を奥まで試して、だめなら戻りたいとき (迷路、組み合わせの全探索)
- 頂点の行き止まりの順を使いたいとき (作業の順番を決める並べ替え)
向いていないとき
- 辺の数で数えて、いちばん近い道を求めたいとき (幅優先探索を使う)
- 辺ごとに長さが違う最短の道を求めたいとき (ダイクストラ法を使う)
コード
疑似コード
- 1visit(s) を呼ぶ (s は開始の頂点)
- 2visit(u) は、まず u を訪問済みにする
- 3u の隣 v を、名前の順に 1 つずつ見る
- 4まだの v は、visit(v) を呼んで奥へ進む
- 5訪問済みの v は、何もしない
- 6隣を全部見終えたら、呼び出し元へ戻る
実際のコード
python実行可能
出力
▶ 実行ボタンを押すと結果がここに表示されます
Python と JavaScript は、書き換えて「実行」を押すと、その場で結果が出ます。Java は読むだけの欄です。
よくある疑問
- 幅優先探索と、訪れる順はどう違いますか？
- 幅優先探索は開始の頂点に近い順、深さ優先探索は行ける所まで奥へ進む順です。同じ木でも、幅優先は A B C D E F G、深さ優先は A B D E C F G になります。
- 再帰を使わずに書けますか？
- 道を自分でスタックに持てば書けます。ただし、頂点を積むときではなく取り出すときに印を付ける形にすると、訪れる順が再帰と変わることがあります。初めは再帰の形が読みやすいです。
- なぜ戻る歩があるのですか？
- 隣を全部見終えた頂点は、もう奥へ進めません。道から外して、1 つ手前の頂点に戻り、そこで残っている隣を見ます。この戻りが、再帰の関数が終わって呼び出し元へ戻ることにあたります。
