C++でグラフの橋（エッジ接続）を検出するプログラムの解説

本記事では、グラフ理論における重要な概念である「橋（ブリッジ）」、すなわちグラフのエッジ接続（Edge Connectivity）をC++で検出する方法を解説します。

橋（ブリッジ）とは？

グラフにおける「橋」とは、その辺を取り除くとグラフが非連結（切断された状態）になってしまうような辺のことです。無向グラフから橋を削除すると、連結成分の数が増加します。つまり、橋はグラフ全体の連結性を保つ上で重要な役割を持つ辺だと言えます。

この問題は、DFS（深さ優先探索）を利用したTarjanのアルゴリズムの考え方を使うことで効率的に解くことができます。各頂点に対して「発見時刻（disc）」と「到達可能な最小の時刻（low）」を記録し、子の部分木から親以上の頂点へ戻れる経路が存在しない場合、その親子間の辺が橋であると判定します。

アルゴリズムの流れと擬似コード

Begin
    関数 connections()：橋を見つけるための再帰関数
    A) 現在のノードを訪問済みとしてマークする
    B) 発見時刻（disc）と low 値を初期化する
    C) この頂点に隣接するすべての頂点を走査する
    D) x を根とする部分木が、w の祖先のいずれかに接続できるかを確認する。
       DFS 木において、x の部分木から到達できる最も上位の頂点が w よりも
       下にある場合、辺 w-x は橋である。
    E) 親関数呼び出しのために w の low 値を更新する
End
Begin
    関数 Con()：connections() を利用して実行する
    A) すべての頂点を未訪問としてマークする
    B) par・visited・各配列を初期化する
    C) グラフの辺の中から橋となっているものを出力する
End

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); // u を v のリストに追加
    adj[w].push_back(x); // v を u のリストに追加
}
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 の部分木から到達できる最上位の頂点が 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 << "\nConnections in first graph \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;
}

実行結果

Connections in first graph
2 3
1 2
1 4
0 1

結果の読み方

出力された各行は「橋となっている辺」を表しています。例えば「2 3」は、頂点2と頂点3をつなぐ辺を取り除くとグラフが分断されることを意味します。同様に「1 4」「0 1」もそれぞれ削除時に連結成分が増える重要な辺です。

このアルゴリズムの計算量は、DFSを一度実行するだけなので O(V + E)（Vは頂点数、Eは辺数）であり、大規模なグラフに対しても効率的に動作します。ネットワークの脆弱性分析や通信網の信頼性評価など、さまざまな分野で応用されている手法です。