関節点と橋の発見 (DFSベース)

**関節点と橋の発見 (DFSベース)**は、一つの経路を進めるだけ進み、行き止まりで戻るグラフ探索である。

仕組み

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

計算量・性質

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

具体例

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

限界と注意点

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