グラフにおける橋（ブリッジ）とは？DFSによる検出アルゴリズムとC++実装

グラフにおける橋（ブリッジ）とは

無向グラフにおいて、ある辺を取り除いたときにグラフが非連結になるとき、つまりグラフが複数の連結成分に分割されるとき、その辺は「橋（ブリッジ）」と呼ばれます。

実用的な観点で考えると、ネットワーク内に橋が存在する場合、その接続が切断されるとネットワーク全体が分断されてしまう可能性があります。そのため、通信網や道路網などの信頼性・耐障害性を評価するうえで、橋の検出は非常に重要な問題となります。

入力と出力

入力:
グラフの隣接行列

0 1 1 1 0
1 0 1 0 0
1 1 0 0 0
1 0 0 0 1
0 0 0 1 0

出力:
与えられたグラフの橋:
Bridge 3--4
Bridge 0--3

橋を見つけるアルゴリズム

このアルゴリズムは深さ優先探索（DFS）をベースにしています。各頂点に対して次の2つの値を管理します。

• disc[頂点]：DFSでその頂点を最初に発見した時刻
• low[頂点]：その頂点から到達できる頂点の中で最も早い発見時刻（後退辺も含む）

頂点 start に隣接する頂点 v を根とする部分木から、start またはその祖先へ戻る辺（後退辺）が存在しない場合、すなわち low[v] > disc[start] が成り立つとき、辺 (start, v) を取り除くと部分木側が孤立するため、この辺は橋であると判定できます。

疑似コード

bridgeFind(start, visited, disc, low, parent)

Begin
    time := 0        // time の値は次回以降の関数呼び出しでも初期化しない
    start を訪問済みとしてマーク
    disc[start] := time + 1、low[start] := time + 1 とする
    time := time + 1

    グラフ G 内のすべての頂点 v について
        辺 (start, v) が存在する場合
            v が未訪問であれば
                parent[v] := start
                bridgeFind(v, visited, disc, low, parent) を呼び出す
                low[start] := low[start] と low[v] の小さい方

                もし low[v] > disc[start] ならば
                    start -- v が橋であることを表示
            そうでなく v が start の親でなければ
                low[start] := low[start] と disc[v] の小さい方
    繰り返しここまで
End

入力 −　探索を始める頂点、訪問済みかどうかを記録する visited 配列、頂点の発見時刻を保持する disc、部分木から到達可能な最も早い発見時刻を保持する low、現在の頂点の親を保持する parent。
出力 −　橋が見つかった場合に、その辺を出力します。

C++による実装例

#include<iostream>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
    {0, 1, 1, 1, 0},
    {1, 0, 1, 0, 0},
    {1, 1, 0, 0, 0},
    {1, 0, 0, 0, 1},
    {0, 0, 0, 1, 0}
};

int min(int a, int b) {
    return (a<b)?a:b;
}

void bridgeFind(int start, bool visited[], int disc[], int low[], int parent[]) {
    static int time = 0;
    visited[start] = true;              // 最初の頂点を訪問済みにする
    disc[start] = low[start] = ++time;  // 発見時刻と low 値を初期化

    for(int v = 0; v<NODE; v++) {
        if(graph[start][v]) {           // start に接続されたすべての頂点 v について
            if(!visited[v]) {
                parent[v] = start;      // start ノードを親として設定
                bridgeFind(v, visited, disc, low, parent);

                low[start] = min(low[start], low[v]);  // v の部分木が start の親につながっている場合
                if(low[v] > disc[start])
                    cout << "Bridge " << start << "--"<<v<<endl;
            } else if(v != parent[start])   // 既に訪問済みの場合は low 値を更新
                low[start] = min(low[start], disc[v]);
        }
    }
}

bool bridges() {
    bool *vis = new bool[NODE];
    int *disc = new int[NODE];
    int *low = new int[NODE];
    int *parent = new int[NODE];

    for(int i = 0; i<NODE; i++) {
        vis[i] = false;     // どのノードも未訪問
        parent[i] = -1;     // 初期状態では親を持たない
    }

    for(int i = 0; i<NODE; i++)
        if(!vis[i])         // 未訪問のノードがあれば、グラフは非連結
            bridgeFind(i, vis, disc, low, parent);
}

int main() {
    cout << "Bridges in given graph:"<<endl;
    bridges();
}

実行結果

Bridges in given graph:
Bridge 3--4
Bridge 0--3

計算量

このアルゴリズムは各頂点と各辺をそれぞれ高々1度ずつ処理するため、時間計算量は頂点数を V、辺数を E として O(V + E) となります。大規模なグラフに対しても効率的に橋を検出できることがわかります。