C++でグラフの関節点（カット頂点）を検出するプログラム

グラフの頂点連結性を調べるには、そのグラフの関節点を特定する必要があります。関節点とは、その頂点（およびそれに接続する辺）を取り除くとグラフが分断されてしまう頂点のことです。非連結な無向グラフの場合、ある頂点を削除したときに連結成分の数が増加するならば、その頂点は関節点であるとみなされます。

アルゴリズム

ここではDFS（深さ優先探索）を用いて関節点を検出します。DFSにおいて、頂点wが次のいずれかの条件を満たすとき、wは関節点となります。

1. wがDFS木の根であり、かつ2つ以上の子を持つ。
2. wがDFS木の根ではなく、子xを持ち、wを根とする部分木内のどの頂点からも、木におけるwの祖先への後退辺が存在しない。

サンプルコード

#include<iostream>
#include <list>
#define N -1
using namespace std;
class G {
    int n;
    list<int> *adj;
    // 関数の宣言
    void APT(int v, bool visited[], int dis[], int low[],
    int par[], bool ap[]);
public:
    G(int n); // コンストラクタ
    void addEd(int w, int x);
    void AP();
};
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::APT(int w, bool visited[], int dis[], int low[], int
par[], bool ap[]) {
    static int t=0;
    int child = 0; // DFS木の子の数を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]) {
            child++;
            par[x] = w;
            APT(x, visited, dis, low, par, ap);
            low[w] = min(low[w], low[x]);
            // 次の場合、w は関節点となる：
            // w がDFS木の根で、2つ以上の子を持つ場合
            if (par[w] == N && child > 1)
                ap[w] = true;
            // w が根でなく、ある子のlow値が w の発見値以上の場合
            if (par[w] != N && low[x] >= dis[w])
                ap[w] = true;
        }
        else if (x != par[w]) // low値を更新
        low[w] = min(low[w], dis[x]);
    }
}
void G::AP() {
    // すべての頂点を未訪問としてマーク
    bool *visited = new bool[n];
    int *dis = new int[n];
    int *low = new int[n];
    int *par = new int[n];
    bool *ap = new bool[n];
    for (int i = 0; i < n; i++) {
        par[i] = N;
        visited[i] = false;
        ap[i] = false;
    }
    // 頂点 i を根とするDFS木に対して APT() を呼び出し、関節点を検出
    for (int i = 0; i < n; i++)
        if (visited[i] == false)
            APT(i, visited, dis, low, par, ap);
    // 関節点を出力
    for (int i = 0; i < n; i++)
        if (ap[i] == true)
            cout << i << " ";
}
int main() {
    cout << "\nArticulation points in first graph \n";
    G g1(5);
    g1.addEd(1, 2);
    g1.addEd(3, 1);
    g1.addEd(0, 2);
    g1.addEd(2, 3);
    g1.addEd(0, 4);
    g1.AP();
    return 0;
}

実行結果

Articulation points in first graph
0 2

解説

この例では、頂点0と頂点2を取り除くとグラフが複数の連結成分に分断されるため、これらが関節点として検出されています。本アルゴリズムは各頂点を一度だけ訪問するDFSに基づいているため、計算量は頂点数V・辺数Eに対してO(V+E)となり、大規模なグラフでも効率的に関節点を求められます。