あったこといろいろ

ほぼ自分用備忘録です。

橋・二重辺連結成分分解

この記事は、Competitive Programming Advent Calendar 2016の記事……ではなく、僕のAdCの記事を楽しむための予備知識として書かれた記事です。
ちなみに、僕の担当は明後日です。よろしくおねがいします。



グラフ上の「橋*1」となる辺を求め、これによりグラフを複数の「二重辺連結成分*2」に分解する方法を解説します。
補足を注釈に書いていたりするので、適宜参照して下さい。

アルゴリズム

前置き

橋は、imos法を用いた方法*3やlowlinkを使う方法*4で列挙することができ、橋を取り除いたグラフでDFSをすることで二重辺連結成分に分解できます。
一方ここでは、Spaghetti Sourceのコードに基づいた、DFSをしながら橋と二重辺連結成分をまとめて列挙する方法を解説します。

以下の説明では「DFS木」や「後退辺」といった用語の説明は省きます。
その辺りの知識が不安な場合、npcaの部誌(2014)のP25あたりを読むと良いと思います。(ちなみに、この部誌ではlowlinkを使った橋の列挙方法を解説しています。)

解説

与えられたグラフ上の適当な頂点からDFSを行い、DFS木を作成します。
この作業の途中に、辺(u,v)*5を辿った先がusedである場合、この辺は後退辺であり、頂点u〜頂点vは同じ二重辺連結成分であることがわかります*6
この処理をDFSをしながら繰り返すことで、二重辺連結成分を列挙できます。また、二重辺連結成分に含まれていない辺は全て橋となっているため、橋を列挙できます。
f:id:Yazaten:20160726190852p:plain
u(8,5)が後退辺であるため、頂点5,7,8は同じ二重辺連結成分であることがわかります。

実装

アルゴリズム」の章では大まかな動作を解説しました。ここでは、具体的な実装を解説します。

はじめに、使用するデータ構造についての解説を以下に示します。

変数名 説明
vector<int> order 各頂点に訪れた順番
stack<int> S 既に訪れた頂点のうち、まだどの二重辺連結成分にも割り振られていない頂点の集合
vector<bool> inS 集合Sに各頂点が含まれているかどうかの情報
stack<int> roots 各二重辺連結成分を、DFS木の部分木として見た時の根の集合


適当な頂点を根としてDFSを開始します。
以下の解説では、現在訪れている頂点をcurと呼び、一つ前に訪れた頂点をprevと呼びます。

新しい頂点を訪れる度に以下の動作を行います。

  • order[cur]にorder[prev]+1を代入することで、その頂点に訪れた順番を記録
  • 集合Sにcurを追加し、curを追加したことをinSに記録
  • rootsにcurを追加


使おうとした辺(cur,to)が後退辺である場合(つまり「to!=prev && inS[to]」の場合 )、以下の動作を行います。

  • cur〜toまでの頂点(ただしtoは含まない)をrootsから捨てる


roots.top()の頂点より葉側の頂点の訪問が終了した場合(つまり「cur==roots.top()」の場合)、以下の動作を行います。
なお説明のため、roots.top()の頂点を以下ではnodeと呼びます。

  • nodeと、DFS木上でnodeより1つだけ根側にある頂点を橋として記録する(nodeが根である場合はなにもしない)
  • 一度目にnodeに訪問してから、nodeに戻ってくるまでに訪問した頂点をすべて同じ連結成分分解として記録する。(S.top()がnodeで無い間、topの値を記録し続けることで実現できる。)
  • rootsのtopの格納されている頂点をpopする


上記の動作を行うことによって最終的に、bridge関数の引数であるbrgに橋のリストが、each_bccに二重連結成分のリストが、cmpにある頂点がどの二重連結成分に含まれているかの情報が格納される。


*1:グラフから取り除いた時に連結成分が増える辺

*2:任意の辺を取り除いても連結であるような部分グラフ

*3:二重辺連結成分分解 ライブラリ - ゆらのふなびと

*4:二辺連結成分分解 - コードを短く書く人のブログ

*5:DFS中木上で根に近い方の頂点をvとする

*6:DFS木上の任意の後退辺(u,v)を考えると、vは必ずuの親となります。