グラフにおける橋(bridge)を検出するアルゴリズム

2020年2月15日2020年9月2日グラフグラフ,競プロ,関節点,切断点,橋,lowlink,DFS

無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」を橋と言います。

※「連結」とは任意の2頂点間を行き来できることを言い、「非連結」は逆に行き来できない頂点があることを言います。（くわしくはグラフを参照）

以下の図の赤い部分が「橋」の例です。

元々が連結でない無向グラフについては、「取り除いたときに非連結成分の数が増える辺」を橋とします。

アルゴリズム

※ 辺を取り除いてみてグラフが非連結になるかどうかを、全ての辺について確かめれば良いです。

※ Union-Find Tree についてはこちらを参照
※ こちらも辺を取り除いてみてグラフが非連結になるかどうかを、全ての辺について確かめれば良いです。

※ DFS tree (深さ優先探索木)は、DFSでグラフを探索する際に通る辺や頂点の集合のことです。これは木になっています。

※ 上述のアルゴリズムは、以下の「 (u,v) が橋となる条件」が元になっています。

1. u が子として以下を満たす頂点 v を持つ
   • v を根とする DFS tree の部分木において、u や u の祖先への後退辺を持つ頂点が存在しない

※ ある点 u が関節点(Articulation Points)であるときは以下のどちらかを満たします。

1. u が DFS tree の根(root) で、子が2つ以上存在する
2. u が DFS tree の根(root) でなく、頂点 u のある子 v について ord[u] ≤ low[v] を満たす

計算量

• 単純なアルゴリズム：O(V(V+E))
• lowlink を用いたアルゴリズム：O(V+E)

※ Union-Find Tree を用いたアルゴリズムは、O(V(V+E)) と微妙に異なりますがほとんど変わりません。

C++での実装例

struct Edge {
    int to;
};
using Graph = vector<vector<Edge>>;
using P = pair<long, long>;

/* Lowlink: グラフの関節点・橋を列挙する構造体
    作成: O(E+V)
    関節点の集合: vector<int> aps
    橋の集合: vector<P> bridges
*/
struct LowLink {
    const Graph &G;
    vector<int> used, ord, low;
    vector<int> aps;  // articulation points
    vector<P> bridges;

    LowLink(const Graph &G_) : G(G_) {
        used.assign(G.size(), 0);
        ord.assign(G.size(), 0);
        low.assign(G.size(), 0);
        int k = 0;
        for (int i = 0; i < (int)G.size(); i++) {
            if (!used[i]) k = dfs(i, k, -1);
        }
        sort(aps.begin(), aps.end()); // 必要ならソートする
        sort(bridges.begin(), bridges.end()); // 必要ならソートする
    }

    int dfs(int id, int k, int par) { // id:探索中の頂点, k:dfsで何番目に探索するか, par:idの親
        used[id] = true;
        ord[id] = k++;
        low[id] = ord[id];
        bool is_aps = false;
        int count = 0; // 子の数
        for (auto &e : G[id]) {
            if (!used[e.to]) {
                count++;
                k = dfs(e.to, k, id);
                low[id] = min(low[id], low[e.to]);
                if (par != -1 && ord[id] <= low[e.to]) is_aps = true; 
                if (ord[id] < low[e.to]) bridges.emplace_back(min(id, e.to), max(id, e.to)); // 条件を満たすので橋  
            } else if (e.to != par) { // eが後退辺の時
                low[id] = min(low[id], ord[e.to]);
            }
        }
        if (par == -1 && count >= 2) is_aps = true; 
        if (is_aps) aps.push_back(id);
        return k;
    }
};

グラフ上の橋の意味

グラフをネットワークとして考えると、橋はネットワーク上の脆弱性を表現しています。その辺に障害が発生して使えなくなると、ネットワークが非連結になってしまい問題となります。

よって、ネットワークの信頼性などを考慮する上で、「橋」という概念が用いられます。

練習問題

• AOJ GRL_3_B Bridges
• [AtCoder] ABC 075 C – Bridge