こんにちは。再帰のDFS（深さ優先探索）っていままでよくわからなくて、スタックを使えばBFS（幅優先探索）の書き換えで済むじゃんと思っていました。過去記事でもスタックDFSを使っています。
ただ、スタックDFSは「順番がDFSであること」くらいしか良いことがないのでこれを機に再帰DFSを使えるようになりたいですね。
題材はAOJの
です。これはスタックDFSでは（すんなりとは）解けないので再帰DFSを使う必要があります。
BFSとDFS2種の比較
BFS
- キューを使う。
- 始点に近いノードから探索するので最短経路がわかる
D - Maze Master（ABC151）
G - Gold General Goes on the Grid（アルゴリズム実技検定 PAST3）
スタックDFS
- スタックを使う
- 探索する順番がDFS
C - Many Requirements（ABC165）
AtCoder ABC165-Cをスタック利用DFSで解く - おはやし日記 - 頂点 $u$ を探索するとき、$u$ の子についての情報は使えない
再帰DFS
- 再帰で実装
- 頂点 $u$ を探索するとき、$u$ の子についての情報を使える（←嬉しい！）
関節点と橋
以下のように関節点と橋が定義されています（詳しくは参考サイトへ）
- 関節点 - 頂点 $u$ とそこにつながっている辺を取り除くと連結成分が増える ←→ $u$ は関節点
- 橋 - 辺 $uv$ を取り除くと連結成分が増える ←→ 辺 $uv$ は橋
lowlink
これを求めるのにlowlinkという概念を使います。
- まずグラフにDFSをして訪問順（行きがけ）の番号 $ord$ を振る
- DFSで通らなかった辺を「後退辺」という
- DFS木を根から葉へ進むか（何回でも）、後退辺を高々1回（1回以下）使って行ける頂点の $ord$ のうち最小のものを lowlink という
図解
このようなグラフを用意しました
頂点 $0$ からDFSをしたときの訪問順序 $ord$ を記録します。赤い辺が後退辺です
$lowlink$ は赤字のようになります
関節点と橋の検出
$(u,\ v)$ が橋 $ \Leftrightarrow ord_u < low_v $
橋と関節点, lowlink - Lilliput Steps
頂点$u$ がDFS tree の根であるとき, その次数が1 より大きければ関節点である(明らかに木を(次数) 個の木に分断する.) そうでないとき, 頂点$u$ のある子$v$ について$ord_u \leqq low_v$ が成り立てば頂点$u$ は関節点となる. ($u$ を介して親の方へ進まなければならないから, $u$ が消えると$v$ 以下の部分木は孤立してしまう.)
橋と関節点, lowlink - Lilliput Steps
実装
行きがけ順（preorder）の記録
行きがけ順の番号を求めるには、以下のように書きます
- 頂点 $u$ の番号を確定した後に $u$ の子 $v_1, v_2, \cdots$ の番号を確定する
int V; //頂点数 vector<vector<int>> G(V); //頂点の隣接リスト vector<int> ord_pre(V, INF); //行きがけ順の記録 int pre = 0; //行きがけ順序 void recdfs(int u){ ord_pre[u] = pre; //uの番号を確定する pre++; for(int v: G[u]){ //uから行ける頂点vについて if(ord_pre[v]==INF){ //未訪問ならばuの子なので recdfs(v); //vの番号を確定させる } } }
帰りがけ順（postorder）の記録
帰りがけ順の番号を求めるには、以下のように書きます
- $u$ の子 $v_1, v_2, \cdots$ の番号を確定した後に頂点 $u$ の番号を確定する
int V; //頂点数 vector<vector<int>> G(V); //頂点の隣接リスト vector<int> ord_pre(V, INF); //行きがけ順の記録 vector<int> ord_pos(V, INF); //帰りがけ順の記録 int pre = 0; //行きがけ順序 int pos = 0; //帰りがけ順序 void recdfs(int u){ ord_pre[u] = pre++; //uの行きがけ順を確定する（後置インクリメントを同時にやる） for(int v: G[u]){ //uから行ける頂点vについて if(ord_pre[v]==INF){ //未訪問ならばuの子なので recdfs(v); //vの番号（pre, pos）を確定させる } } ord_pos[u] = pos++; // uの帰りがけ順を確定する }
「$u$ の子 $v_1, v_2, \cdots$ の番号を確定した後」と書きましたがrecdfs(v_1)を実行すると $v_1$ の子 $w_1, w_2, \cdots$ を見た後に $v_1$ の番号を確定しているので実のところは「$u$ の子 $v_1, v_2, \cdots$ を頂点とする部分木の番号を確定した後」に $u$ の番号を確定しています。まさに「帰りがけ」の処理ですね(?)
lowlinkの記録
擬似コード的にlowlinkの処理を書き加えると次のようになります（帰りがけ順の話は終わりなので省略）
int V; //頂点数 vector<vector<int>> G(V); //頂点の隣接リスト vector<int> ord_pre(V, INF); //行きがけ順の記録 vector<int> lowlink(V, INF); //lowlinkの記録 int pre = 0; //行きがけ順序 void recdfs(int u){ ord_pre[u] = pre++; //uの番号を確定する lowlink[u] = ord_pre[u]; for(int v: G[u]){ //uから行ける頂点vについて if(ord_pre[v]==INF){ //未訪問ならばuの子なので recdfs(v); //vの番号を確定させる //vのlowlinkも確定 lowlink[u] = min(lowlink[u], lowlink[v]); }else if( /* 訪問済みだけど辺uvが未使用 */ ){ //このとき uv が後退辺 lowlink[u] = min(lowlink[u], ord_pre[v]); } } }
if( /* 訪問済みだけど辺uvが未使用 */ )を判定するためにはif( /* 訪問済みだけどvがuの親ではない */ )とすれば良いです。そのために、p = uの親ノードをrecdfs()の引数として与える必要があります（根の親ノードは-1とする）。
int V; //頂点数 vector<vector<int>> G(V); //頂点の隣接リスト vector<int> ord_pre(V, INF); //行きがけ順の記録 vector<int> lowlink(V, INF); //lowlinkの記録 int pre = 0; //行きがけ順序 void recdfs(int p, int u){ //p : uの親 ord_pre[u] = pre++; //uの番号を確定する lowlink[u] = ord_pre[u]; for(int v: G[u]){ //uから行ける頂点vについて if(ord_pre[v]==INF){ //未訪問ならばuの子なので recdfs(u, v); //uの子であるvの番号を確定させる //vのlowlinkも確定 lowlink[u] = min(lowlink[u], lowlink[v]); }else if( v != p ){ //このとき uv が後退辺 lowlink[u] = min(lowlink[u], ord_pre[v]); } } }
橋の検出
辺 $uv$ が橋になる必要十分条件はord_pre[u] < lowlink[v]なので
int V; //頂点数 vector<vector<int>> G(V); //頂点の隣接リスト vector<int> ord_pre(V, INF); //行きがけ順の記録 vector<int> lowlink(V, INF); //lowlinkの記録 vector<pair<int, int>> Bridges; //橋のリスト int pre = 0; //行きがけ順序 void recdfs(int p, int u){ //p : uの親 ord_pre[u] = pre++; //uの番号を確定する lowlink[u] = ord_pre[u]; for(int v: G[u]){ //uから行ける頂点vについて if(ord_pre[v]==INF){ //未訪問ならばuの子なので recdfs(u, v); //uの子であるvの番号を確定させる //vのlowlinkも確定 lowlink[u] = min(lowlink[u], lowlink[v]); if(ord_pre[u] < lowlink[v])Bridges.push_back({u,v}); //橋の判定してリストに入れる }else if( v != p ){ //このとき uv が後退辺 lowlink[u] = min(lowlink[u], ord_pre[v]); } } }
関節点の検出
前の方で紹介した通り、関節点の判定は「DFS木の根かどうか」で場合分けがあります
- 根のとき : 「DFS木の」次数が1より大きい
- それ以外 :
ord_pre[u]<=lowlink[v]となる子 $v$ がある
int V; //頂点数 vector<vector<int>> G(V); //頂点の隣接リスト vector<int> ord_pre(V, INF); //行きがけ順の記録 vector<int> lowlink(V, INF); //lowlinkの記録 vector<pair<int, int>> Bridges; //橋のリスト vector<int> ArticulationPoints; //関節点のリスト int pre = 0; //行きがけ順序 void recdfs(int p, int u){ //p : uの親 ord_pre[u] = pre++; //uの番号を確定する lowlink[u] = ord_pre[u]; int cnt = 0; //DFS木次数カウント bool isArt = false; //関節点か否か for(int v: G[u]){ //uから行ける頂点vについて if(ord_pre[v]==INF){ //未訪問ならばuの子なので cnt++; recdfs(u, v); //uの子であるvの番号を確定させる //vのlowlinkも確定 lowlink[u] = min(lowlink[u], lowlink[v]); if(ord_pre[u] < lowlink[v])Bridges.push_back({u,v}); //橋の判定してリストに入れる if(p!=-1 && ord_pre[u]<=lowlink[v])isArt = true; //根以外の関節点判定 }else if( v != p ){ //このとき uv が後退辺 lowlink[u] = min(lowlink[u], ord_pre[v]); } } if(p==-1 && cnt>1)isArt = true; //根の関節点判定 if(isArt)ArticulationPoints.push_back(u); //関節点だったらリストに入れる }
一応メイン関数とか
出力部分を3a（関節点）と3b（橋）で使い分ければACになります
#include <bits/stdc++.h> using namespace std; #define INF 1<<29 #define all(v) (v).begin(), (v).end() int V, E; //頂点数 辺の数 vector<vector<int>> G(V); //頂点の隣接リスト vector<int> ord_pre(V, INF); //行きがけ順の記録 vector<int> lowlink(V, INF); //lowlinkの記録 vector<pair<int, int>> Bridges; //橋のリスト vector<int> ArticulationPoints; //関節点のリスト int pre = 0; //行きがけ順序 void recdfs(int p, int u){ /*省略*/ } int main(){ cin>>V>>E; G.resize(V); for(int i=0; i<E; i++){ int s,t; cin>>s>>t; G[s].push_back(t); G[t].push_back(s); } ord_pre.assign(V, INF); lowlink.assign(V,INF); pre = 0; recdfs(-1, 0); //* 3a sort(all(ArticulationPoints)); for(int x: ArticulationPoints)cout<<x<<endl; //*/ //* 3b for(auto &x: Bridges){ if(x.first>x.second)swap(x.first, x.second); } sort(all(Bridges)); for(auto x: Bridges)cout<<x.first<<" "<<x.second<<endl; //*/ }
まとめ
関節点と橋の判定そのものについては参考サイト見れば分かるんだけど、再帰DFSが怖くないよっていうのがわかったので良かったです
void DFS(頂点 u, 親からの情報 p, 親へ戻す情報 &q){ //行きがけの処理 s = func1(u, p); //下に送る情報 t; //下からくる情報 for(auto v: G[u]){ DFS(v, s, t); //uの子を頂点とする部分木の処理 } //帰りがけの処理 q = func2(u, t); //下からの情報を処理 }
概ねこんな感じにすれば（DFSに限らず）再帰ができる
