Boost.GraphでJR全線乗り尽くしプランを立てる - プログラミング生放送+CLR/H+Sapporo.cpp 勉強会＠札幌 （2014.7.12）
Boost.GraphでJR全線乗り尽くしプランを立てる - プログラミング生放送+CLR/H+Sapporo.cpp 勉強会＠札幌 （2014.7.12）
Boost.GraphでJR全線乗り尽くしプランを立てる - プログラミング生放送+CLR/H+Sapporo.cpp 勉強会＠札幌 （2014.7.12）
橋（bridge）検出アルゴリズム - nupiocaの日記
連結グラフにおいて橋（bridge）とは、それを取り除くと連結でなくなってしまうような辺のこと。閉路に含まれない辺が橋になる。 橋はDFSを行うことで検出することができる。DFSは、アルゴリズムの一部としてグラフの構造を調べる時によく使われる。 アルゴリズム まず、頂点を１つ選び、DFSを開始する。 各頂点には、pre、lowという２つのデータを記録する。 preは、DFS木の行きがけ順（pre-order）の値を保持する。 lowは、DFS木でその頂点から到達しうる頂点のpreの最小値を保持する。初期値はその頂点のpreである。 次の頂点が、すでに訪れてある（preの値が存在する）場合は、自分のlowを、次の頂点のlowと比べて小さい方に更新する。 次の頂点をまだ訪れていない場合は、その頂点に対してDFSを続ける。そして、その頂点へのDFSが終了した際に、lowがpreより小さくなってい
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
