概要
概要
深さ優先探索は、1 本の道を深く追ってから戻る探索です。再帰またはスタックで実装できます。
グラフ / DFS（深さ優先探索）
深さ優先探索は、1 本の道を深く追ってから戻る探索です。再帰またはスタックで実装できます。
目次
このページでわかること
概要
深さ優先探索は、1 本の道を深く追ってから戻る探索です。再帰またはスタックで実装できます。
考え方
visit node
for each unvisited neighbor
dfs(neighbor)要点
O(V + E)
O(V)
Stack / Recursion
全探索, SCC の基礎
補足
近さより深さを優先します。
順序がかなり変わります。
探索木と戻りをセットで見せるとよいです。
動きで確認
ここでは「どの頂点が注目か」を見ながら、上で読んだ内容を動きと結びつけます。
次に見る
比較すると違いがわかりやすいページを先に置いています。