C++で指定された頂点集合から到達可能なすべてのノードを検索する方法

無向グラフと頂点の集合が与えられたとき、その集合に含まれる各頂点から到達可能なすべてのノードを見つけることを考えます。

たとえば、次のようなグラフが入力として与えられた場合：

出力は [1,2,3] と [4,5] になります。これはグラフが2つの連結成分に分かれているためです。

解法のアプローチ

この問題を解くためには、次の手順に従います。

• nodes := グラフ内のノード数を取得する
• サイズが nodes+1 の訪問済み配列 visited を定義し、すべて 0 で初期化する
• 結果を格納するためのマップ m を定義する
• comp_sum := 0（連結成分のカウンタ）
• i := 0 から開始し、i < n の間 i を1ずつ増やしながら以下を繰り返す：
  • u := arr[i]（対象の頂点）
  • visited[u] が false の場合は以下を実行する：
    • comp_sum を1増やす
    • m[visited[u]] := ノード u を起点としたグラフ g のBFS走査結果を保存する（同時に comp_sum も更新される）
  • m[visited[u]] の走査結果を出力する

ポイントは、visited 配列に真偽値ではなく連結成分の番号を記録することです。こうすることで、同じ連結成分に属する頂点に対しては、すでに計算済みの結果をマップから再利用でき、重複した探索を避けることができます。

実装例

理解を深めるために、以下のC++の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;
class Graph{
   public:
      int nodes;
      list<int> *adj_list;
      Graph(int);
      void insert_edge(int, int);
      vector<int> BFS(int, int, int []);
};
Graph::Graph(int nodes) {
   this->nodes = nodes;
   adj_list = new list<int>[nodes+1];
}
void Graph::insert_edge(int u, int v) {
   adj_list[u].push_back(v);
   adj_list[v].push_back(u);
}
vector<int> Graph::BFS(int comp_sum, int src,int visited[]){
   queue<int> queue;
   queue.push(src);
   visited[src] = comp_sum;
   vector<int> reachableNodes;
   while(!queue.empty()) {
      int u = queue.front();
      queue.pop();
      reachableNodes.push_back(u);
      for (auto itr = adj_list[u].begin(); itr != adj_list[u].end(); itr++) {
         if (!visited[*itr]) {
            visited[*itr] = comp_sum;
            queue.push(*itr);
         }
      }
   }
   return reachableNodes;
}
void displayReachableNodes(int n, unordered_map <int, vector<int> > m) {
   vector<int> temp = m[n];
   for (int i=0; i<temp.size(); i++)
      cout << temp[i] << " ";
   cout << endl;
}
void get_all_reachable(Graph g, int arr[], int n) {
   int nodes = g.nodes;
   int visited[nodes+1];
   memset(visited, 0, sizeof(visited));
   unordered_map <int, vector<int> > m;
   int comp_sum = 0;
   for (int i = 0 ; i < n ; i++) {
      int u = arr[i];
      if (!visited[u]) {
         comp_sum++;
         m[visited[u]] = g.BFS(comp_sum, u, visited);
      }
      cout << "Reachable Nodes from " << u <<" are\n";
      displayReachableNodes(visited[u], m);
   }
}
int main() {
   int nodes = 5;
   Graph g(nodes);
   g.insert_edge(1, 2);
   g.insert_edge(2, 3);
   g.insert_edge(4, 5);
   int arr[] = {2, 4, 1};
   int n = sizeof(arr)/sizeof(int);
   get_all_reachable(g, arr, n);
}

入力

g.insert_edge(1, 2);
g.insert_edge(2, 3);
g.insert_edge(4, 5);

出力

Reachable Nodes from 2 are
2 1 3
Reachable Nodes from 4 are
4 5
Reachable Nodes from 1 are
2 1 3

出力結果の解説

頂点2からは「2 1 3」、頂点4からは「4 5」、頂点1からは「2 1 3」が出力されています。頂点1と頂点2は同じ連結成分に属しているため、両者から到達可能なノードの集合は同一になります。また、頂点1の処理時にはすでにBFSの結果がキャッシュされているため、新たな探索は行われず、即座に結果が表示されます。

このアルゴリズムの計算量は O(V + E) です。各頂点と各辺は最大でも1回ずつしか処理されないため、大規模なグラフに対しても効率的に動作します。