グラフの最大カットを求めるC++プログラム ― 辺連結性と橋（ブリッジ）の検出

本記事では、グラフの最大カットを求める問題に関連して、グラフの辺連結性を調べるC++プログラムを紹介します。ここで扱うのは「橋（ブリッジ）」と呼ばれる特別な辺の検出です。

橋（ブリッジ）とは何か？

無向グラフにおける橋（ブリッジ）とは、その辺を取り除いた瞬間にグラフが非連結になってしまう辺のことです。言い換えれば、橋を1本取り除くだけで、グラフの連結成分の数が増加します。この性質を利用すると、ネットワークの中で特に脆弱な箇所（切断されやすいリンク）を特定できます。

アルゴリズムの考え方と擬似コード

橋の検出には、深さ優先探索（DFS）を用いるのが定番です。各頂点に対して「発見時刻（dis）」と「その頂点から辿れる最も早い発見時刻（low）」を記録し、子頂点 x について low[x] > dis[w] が成り立つならば、辺 w–x は橋であると判定できます。

connections() 関数（再帰的に橋を検出）

開始
　　関数 connections() は、橋を見つけるための再帰関数である：
　　A) 現在のノードを訪問済みとしてマークする
　　B) 発見時刻と low 値を初期化する
　　C) この頂点に隣接するすべての頂点を順に処理する
　　D) x を根とする部分木が、w の祖先のいずれかに接続しているかを確認する。
　　   DFS 木において、x の部分木から到達できる最も上位の頂点が w より下にしか
　　   届かない場合、辺 w–x は橋である
　　E) 親への再帰呼び出しのために、w の low 値を更新する
終了

Con() 関数（connections() の呼び出し元）

開始
　　関数 Con() は connections() を利用する：
　　A) すべての頂点を未訪問としてマークする
　　B) par・visited・connections を初期化する
　　C) グラフ中の橋となっている辺を出力する
終了

C++によるサンプルコード

#include<iostream>
#include <list>
#define N -1
using namespace std;
class G {
    //関数の宣言
    int n;
    list<int> *adj;
    void connections(int n, bool visited[], int disc[], int low[], int par[]);
    public:
        G(int n); //コンストラクタ
        void addEd(int w, int x);
        void Con();
};
G::G(int n) {
    this->n= n;
    adj = new list<int> [n];
}
//グラフに辺を追加する
void G::addEd(int w, int x) {
    adj[x].push_back(w); //vのリストにuを追加
    adj[w].push_back(x); //uのリストにvを追加
}
void G::connections(int w, bool visited[], int dis[], int low[],
int par[]) {
    static int t = 0;
    //現在のノードを訪問済みとしてマーク
    visited[w] = true;
    dis[w] = low[w] = ++t;
    //隣接するすべての頂点を走査する
    list<int>::iterator i;
    for (i = adj[w].begin(); i != adj[w].end(); ++i) {
        int x = *i; //xは現在の隣接頂点
        if (!visited[x]) {
            par[x] = w;
            connections(x, visited, dis, low, par);
            low[w] = min(low[w], low[x]);
            // xの部分木から到達できる最上位の頂点がDFS木上でwより下の場合、w-xは橋
            if (low[x] > dis[w])
                cout << w << " " << x << endl;
        } 
        else if (x != par[w])
        low[w] = min(low[w], dis[x]);
    }
}
void G::Con() {
    // すべての頂点を未訪問としてマーク
    bool *visited = new bool[n];
    int *dis = new int[n];
    int *low = new int[n];
    int *par = new int[n];
    for (int i = 0; i < n; i++) {
        par[i] = N;
        visited[i] = false;
    }
    // connections()を呼び出して辺の接続（橋）を検出する
    for (int i = 0; i < n; i++)
        if (visited[i] == false)
            connections(i, visited, dis, low, par);
}
int main() {
    cout << "\n1つ目のグラフの橋 \n";
    G g1(5);
    g1.addEd(1, 2);
    g1.addEd(3, 2);
    g1.addEd(2, 1);
    g1.addEd(0, 1);
    g1.addEd(1, 4);
    g1.Con();
    return 0;
}

実行結果

1つ目のグラフの橋
2 3
1 2
1 4
0 1

計算量について

このアルゴリズムは各頂点と各辺をそれぞれ高々1回ずつ処理するため、時間計算量は O(V + E)、空間計算量は頂点数 V に比例した O(V) となります。大規模なグラフでも効率的に橋を検出できる点が大きな魅力です。ネットワークの信頼性分析や道路網・通信網の冗長性チェックなど、実務的な場面でも幅広く応用されています。