【C++】グラフ内の橋（ブリッジエッジ）の数を検出するプログラムの解説

ブリッジエッジ（橋）とは？

重みなし無向グラフにおけるブリッジエッジ（橋）とは、その辺を取り除いたときにグラフが非連結（複数の連結成分に分断される）となるような辺のことです。本記事では、n個の頂点とm個の辺からなるグラフが与えられたとき、その中に含まれるブリッジの数を求めるC++プログラムを紹介します。なお、対象となるグラフには平行辺や自己ループは含まれないものとします。

問題の例

例として、n = 5、m = 6、edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}} という入力が与えられた場合を考えてみましょう。この場合の出力は 1 となります。

このグラフには、ブリッジエッジ {2, 4} がちょうど1つだけ存在します。辺 {2, 4} を取り除くと、頂点4が他の頂点から切り離されてしまうためです。

解法のアプローチ

この問題は、深さ優先探索（DFS）を利用したTarjanの橋検出アルゴリズムによって効率的に解くことができます。探索の過程で各頂点に対して次の2つの値を記録します。

• vk[v]：頂点vを訪問した順番（タイムスタンプ）
• l[v]：頂点vから後退辺を経由しても到達できる、最も早いタイムスタンプ

そして、木構造の辺 (v, x) について l[x] > vk[v] が成り立つ場合、部分グラフx側からvより上の頂点へ戻る経路が存在しないことを意味するため、その辺はブリッジであると判定できます。

アルゴリズムの手順

mSize := 100
サイズmSizeの隣接リスト配列Gを定義
2次元配列bridgeを定義
サイズmSizeの配列visitedを定義
サイズmSizeの配列vkおよびlを定義
整数ペアを格納する配列edgesを定義

関数depthSearch(v, p = -1)：
   visited[v] := 1
   vk[v] := l[v] := t++
   G[v]内の各xに対して：
      x == p の場合は次の反復へスキップ
      visited[x] が非ゼロの場合：
         l[v] := min(l[v], vk[x])
      それ以外の場合：
         depthSearch(x, v) を再帰呼び出し
         l[v] := min(l[v], l[x])
         l[x] > vk[v] であれば：
            bridge[v][x] := 1

関数bridgeSearch()：
   t := 0
   i := 1 から n まで：
      visited[i] が偽であれば depthSearch(i) を呼び出す

メイン処理：
   i := 0 から m 未満まで：
      a := edges[i] の始点、b := edges[i] の終点
      G[a] に b を追加、G[b] に a を追加（無向グラフなので両方向）
   bridgeSearch() を呼び出す
   ans := 0
   i, j の全組み合わせについて：
      i != j かつ bridge[i][j] が真なら ans をインクリメント
   ans を返す

C++実装例

以下に、上記アルゴリズムの実際のC++コードを示します。

#include <bits/stdc++.h>
using namespace std;

const int mSize = 100;
vector<int> G[mSize];
int n, m, t;
vector<vector<int>> bridge(mSize, vector<int>(mSize));
vector<int> visited(mSize);
vector<int> vk(mSize, -1), l(mSize, -1);
vector<pair<int, int>> edges;

void depthSearch(int v, int p = -1) {
    visited[v] = 1;
    vk[v] = l[v] = t++;
    for (auto x : G[v]) {
        if (x == p) {
            continue;
        }
        if (visited[x]) {
            l[v] = min(l[v], vk[x]);
        } else {
            depthSearch(x, v);
            l[v] = min(l[v], l[x]);
            if (l[x] > vk[v]) {
                bridge[v][x] = 1;
            }
        }
    }
}

void bridgeSearch() {
    t = 0;
    for (int i = 1; i <= n; ++i) {
        if (!visited[i]) {
            depthSearch(i);
        }
    }
}

int solve() {
    for (int i = 0; i < m; ++i) {
        int a, b;
        a = edges[i].first;
        b = edges[i].second;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    bridgeSearch();
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i != j and bridge[i][j]) ans++;
        }
    }
    return ans;
}

int main() {
    n = 5, m = 6;
    edges = {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}};
    cout << solve();
    return 0;
}

入力

5, 6, {{1, 2}, {1, 3}, {2, 3}, {2, 4}, {2, 5}, {3, 5}}

出力

1

計算量の考察

DFSを1回実行するだけで済むため、探索自体の計算量は O(V + E)（Vは頂点数、Eは辺数）と非常に効率的です。ただし、上記のコードでは最後に隣接行列bridgeを二重ループで走査してブリッジをカウントしているため、全体としてはO(V² + E)となります。大規模なグラフを扱う場合は、ブリッジを検出した時点で直接カウントするように変更すれば、計算量をO(V + E)に抑えることが可能です。