C++の特定のセットに存在するすべてのノードから到達可能なすべてのノードを検索します

1つの無向グラフと一連の頂点があるとします。与えられたセットに存在するすべての頂点から到達可能なすべてのノードを見つける必要があります。

したがって、入力が次のような場合

この場合、出力は[1,2,3]と[4,5]になります。これは、これらが2つの連結成分であるためです。

これを解決するには、次の手順に従います-

• ノード：=グラフ内のノードの数
• 訪問したサイズの配列を定義します：nodes+1。そして0で埋める
• 1つのマップを定義するm
• comp_sum：=0
• iを初期化する場合：=0、i
• u：=arr [i]
• visited [u]がfalseの場合、-
  • （comp_sumを1増やします）
  • m [visited [u]]：=ノードuからのgのbfsトラバーサル、comp_sumも計算します
• m [visited [u]]
の走査を印刷します

例

理解を深めるために、次の実装を見てみましょう-

#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