おはやし日記

特にテーマ無しの日記。

グラフの関節点と橋を求めて再帰DFSを知る

こんにちは。再帰のDFS(深さ優先探索)っていままでよくわからなくて、スタックを使えばBFS(幅優先探索)の書き換えで済むじゃんと思っていました。過去記事でもスタックDFSを使っています。

o-treetree.hatenablog.com

ただ、スタックDFSは「順番がDFSであること」くらいしか良いことがないのでこれを機に再帰DFSを使えるようになりたいですね。

題材はAOJの

です。これはスタックDFSでは(すんなりとは)解けないので再帰DFSを使う必要があります。

BFSとDFS2種の比較

BFS

スタックDFS

再帰DFS

  • 再帰で実装
  • 頂点 $u$ を探索するとき、$u$ の子についての情報を使える(←嬉しい!)

関節点と橋

以下のように関節点と橋が定義されています(詳しくは参考サイトへ)

  • 関節点 - 頂点 $u$ とそこにつながっている辺を取り除くと連結成分が増える ←→ $u$ は関節点
  • 橋 - 辺 $uv$ を取り除くと連結成分が増える ←→ 辺 $uv$ は橋

これを求めるのにlowlinkという概念を使います。

  • まずグラフにDFSをして訪問順(行きがけ)の番号 $ord$ を振る
  • DFSで通らなかった辺を「後退辺」という
  • DFS木を根から葉へ進むか(何回でも)、後退辺を高々1回(1回以下)使って行ける頂点の $ord$ のうち最小のものを lowlink という

図解

このようなグラフを用意しました

f:id:o-treetree:20200607121936j:plain

頂点 $0$ からDFSをしたときの訪問順序 $ord$ を記録します。赤い辺が後退辺です

f:id:o-treetree:20200607121952j:plain

$lowlink$ は赤字のようになります

f:id:o-treetree:20200607122001j:plain

関節点と橋の検出

$(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に限らず)再帰ができる

グラフ情報

graph lowlink example

参考

プライバシーポリシー ・お問い合わせはこちら