DFSの性質 (閉路検出、トポロジカルソート、強連結成分)

**DFSの性質 (閉路検出、トポロジカルソート、強連結成分)**は、一つの経路を進めるだけ進み、行き止まりで戻るグラフ探索である。

仕組み

再帰または明示的スタックで未訪問隣接頂点へ進み、各頂点の発見・完了状態を管理する。

計算量・性質

隣接リストではO(V+E)、訪問集合とスタックにO(V)。

具体例

経路A-B-Dを進んで戻り、次にA-Cを調べるように探索する。

限界と注意点

深いグラフでは再帰スタックが枯渇し得る。閉路がある場合は訪問管理が必須。