グラフの関節点（アーティキュレーションポイント）を検出するC++プログラム

グラフにおける関節点（Articulation Point、カット頂点とも呼ばれます）とは、その頂点（およびそれに接続する辺）を取り除くとグラフが分断されてしまう頂点のことです。非連結な無向グラフの場合は、その頂点を削除すると連結成分の数が増加する頂点が関節点に該当します。

アルゴリズム

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

1. w が DFS ツリーのルートであり、少なくとも2つの子を持つ場合
2. w が DFS ツリーのルートではなく、w を根とする部分木内のどの頂点からも、w の祖先への後退辺（バックエッジ）が存在しない子 x を持つ場合

サンプルコード

#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); // vのリストにuを追加
   adj[w].push_back(x); // uのリストにvを追加
}
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

この実行結果から、サンプルグラフ（5頂点の無向グラフ）における関節点は頂点0と頂点2であることがわかります。頂点0を削除すると頂点4が孤立し、頂点2を削除するとグラフが分断されるためです。

このアルゴリズムの計算量は、各頂点と各辺をそれぞれ1回ずつ走査するため O(V + E) です。ここで V は頂点数、E は辺数を表します。Tarjan のアルゴリズムとして知られるこの手法は、ネットワークの脆弱性解析や通信経路の冗長性チェックなど、さまざまな分野で応用されています。