橋（bridge）検出アルゴリズム - nupiocaの日記

連結グラフにおいて橋（bridge）とは、それを取り除くと連結でなくなってしまうような辺のこと。閉路に含まれない辺が橋になる。 橋はDFSを行うことで検出することができる。DFSは、アルゴリズムの一部としてグラフの構造を調べる時によく使われる。 アルゴリズム まず、頂点を１つ選び、DFSを開始する。 各頂点には、pre、lowという２つのデータを記録する。 preは、DFS木の行きがけ順（pre-order）の値を保持する。 lowは、DFS木でその頂点から到達しうる頂点のpreの最小値を保持する。初期値はその頂点のpreである。 次の頂点が、すでに訪れてある（preの値が存在する）場合は、自分のlowを、次の頂点のlowと比べて小さい方に更新する。 次の頂点をまだ訪れていない場合は、その頂点に対してDFSを続ける。そして、その頂点へのDFSが終了した際に、lowがpreより小さくなってい

[Kuromaku]

グラフ理論