強連結成分



連結な有向グラフで、有向閉路が存在するとき、ノード同士の関係には、相互に到達可能な関係と、片方のノードから到達可能ながらその逆は到達不能であるような関係の2種類が存在する。相互に到達可能なノードの組を強連結成分とすると、連結な有向グラフは1つ以上の強連結成分に分けられ、強連結成分同士は、一方通行のエッジで結ばれる。強連結成分は深さ優先探索を修正した方法で検出することができるので、深さ優先探索と同様に線形時間の処理となる