グラフを切断するために除去すべき最小のエッジ（橋）を見つけるC++プログラム

本記事では、グラフの辺連結性に関わる「橋（ブリッジ）」を検出するC++プログラムを紹介します。グラフにおける橋とは、その辺を1本取り除くだけでグラフが非連結（切断状態）になってしまう辺のことです。無向グラフから橋を取り除くたびに連結成分の数が増加するため、「グラフを切断するために必要な最小のカット辺を見つける」という問題は、この橋の検出に他なりません。

アルゴリズムの考え方

橋の検出には、DFS（深さ優先探索）をベースとしたタージャン（Tarjan）のアルゴリズムを使用します。各頂点に対して次の2つの値を管理するのがポイントです。

• disc[]： DFSでその頂点を発見した時刻
• low[]： その頂点およびその部分木から到達できる最も早い時刻（祖先への後退辺を含む）

辺 w–x について、x の部分木から w やその祖先へ戻る経路が存在しない（low[x] > disc[w] となる）場合、w–x は橋であると判定できます。計算量は O(V + E) と効率的です。

connections() 関数の擬似コード

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

Con() 関数の擬似コード

開始
    関数 Con()：connections() を利用して橋を検出する
    A) すべての頂点を未訪問としてマークする
    B) par・visited・disc・low などの配列を初期化する
    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); // w を x の隣接リストに追加
    adj[w].push_back(x); // x を w の隣接リストに追加
}
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 << "\n最初のグラフの橋 \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;
}

実行結果

最初のグラフの橋
2 3
1 2
1 4
0 1

コードのポイント

• グラフは隣接リスト（list<int> の配列）で表現しています。
• static 変数 t により、DFS 全体で共通の時刻を管理します。
• low[x] > dis[w] が成り立つ場合のみ、w–x を橋として出力します。
• 訪問済みかつ親ではない頂点への辺（後退辺）の場合は、low[w] を更新して祖先への接続を記録します。
• 連結でないグラフにも対応できるよう、すべての頂点を起点に DFS を実行しています。