深さ優先探索(DFS)

深さ優先探索とは

深さ優先探索(Depth First Search: DFS)とは、可能な限り隣接する頂点を訪問するという戦略に基づくアルゴリズムである。未探索の接続辺が残されている頂点の中で最後に発見した頂点 \(v\) の接続辺を再帰的に探索する。\(v\) の辺をすべて探索し終えると、\(v\) を発見したときに通ってきた辺を後戻りして探索を続行する。

【出典】
渡部有隆, Ozy, 秋葉拓哉他「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」273〜281頁