C++でネットワーク上の重要な接続(橋)を検出するアルゴリズム

n台のサーバーがあり、それぞれ0からn-1までの番号が付けられているとします。これらのサーバーは無向の接続によってネットワークを形成しており、connections[i] = [a, b] はサーバーaとサーバーbの間の接続を表します。すべてのサーバーは、直接または他のサーバーを経由して相互に到達できる状態になっています。

ここで「重要な接続(クリティカルコネクション)」とは、その接続を取り除いたときに、あるサーバーから別のサーバーへ到達できなくなるような接続のことです。本記事では、このような重要な接続をすべて見つける方法を解説します。

問題例

例として、入力が n = 4、connections = [[0,1],[1,2],[2,0],[1,3]] のケースを考えてみましょう。

この場合の出力は [[1,3]] となります。サーバー1とサーバー3を結ぶ接続を取り除くと、サーバー3が他のサーバーから完全に孤立してしまうためです。一方、それ以外の接続には代替経路が存在するため、重要な接続とはなりません。

解決アプローチ

この問題は、グラフ理論における「橋(ブリッジ)」の検出問題と同一であり、Tarjanのアルゴリズムを用いたDFS(深さ優先探索)によって O(V + E) の計算量で効率的に解くことができます。手順は以下の通りです。

• 訪問済みノードを管理するセット visited を定義する
• 各ノードが最初に発見された時刻を記録する配列 disc を定義する
• 各ノードから到達可能な最小の発見時刻を記録する配列 low を定義する
• 結果を格納する2次元配列 ret を定義する
• node、par(親ノード)、graph を引数に取る関数 dfs() を定義する

dfs() 関数の処理内容

• node がすでに visited に含まれている場合は、そのまま return する
• node を visited に挿入する
• disc[node] := time、low[node] := time とし、time を1増やす
• graph[node] 内のすべての要素 x について以下を繰り返す
  • x が par(親ノード)と同じ場合は、現在の反復をスキップする
  • x が未訪問の場合:
    • dfs(x, node, graph) を再帰呼び出しする
    • low[node] := min(low[node], low[x]) で更新する
    • disc[node] < low[x] が成り立つ場合、{ node, x } を ret の末尾に追加する(これは重要な接続)
  • それ以外の場合:
    • low[node] := min(low[node], disc[x]) で更新する

メイン関数での処理

• disc および low のサイズを n + 1 に設定する
• time := 0 で初期化する
• サイズ n + 1 の隣接リスト graph を作成する
• 接続情報 v を走査し、双方向のエッジを graph に登録する
• dfs(0, -1, graph) を実行する
• ret を返す

以下の実装例を見ると、より理解が深まるでしょう。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
   cout << "[";
   for(int i = 0; i<v.size(); i++){
      cout << "[";
      for(int j = 0; j <v[i].size(); j++){
         cout << v[i][j] << ", ";
      }
      cout << "],";
   }
   cout << "]"<<endl;
}
class Solution {
   public:
   set<int> visited;
   vector<int> disc;
   vector<int> low;
   int time;
   vector<vector<int> > ret;
   void dfs(int node, int par, vector<int> graph[]) {
      if (visited.count(node))
      return;
      visited.insert(node);
      disc[node] = low[node] = time;
      time++;
      for (int x : graph[node]) {
         if (x == par)
         continue;
         if (!visited.count(x)) {
            dfs(x, node, graph);
            low[node] = min(low[node], low[x]);
            if (disc[node] < low[x]) {
               ret.push_back({ node, x });
            }
         } else{
            low[node] = min(low[node], disc[x]);
         }
      }
   }
   vector<vector<int> > criticalConnections(int n, vector<vector<int> >& v) {
      disc.resize(n + 1);
      low.resize(n + 1);
      time = 0;
      vector<int> graph[n + 1];
      for (int i = 0; i < v.size(); i++) {
         int u = v[i][0];
         int w = v[i][1];
         graph[u].push_back(w);
         graph[w].push_back(u);
      }
      dfs(0, -1, graph);
      return ret;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{0,1},{1,2},{2,0},{1,3}};
   print_vector(ob.criticalConnections(4,v));
}

入力

4, {{0,1},{1,2},{2,0},{1,3}}

出力

[[1, 3]]