C++での切断されたグラフのBFS

切断されたグラフ は、1つ以上のノードがグラフの端点ではない、つまり接続されていないグラフです。

切断されたグラフ…

現在、Simple BFSは、グラフが接続されている場合、つまりグラフのすべての頂点にグラフの1つのノードからアクセスできる場合にのみ適用できます。上記の切断されたグラフの手法では、いくつかの法則にアクセスできないため不可能です。したがって、切断されたグラフで幅優先探索を実行するには、次の変更されたプログラムの方が適しています。

例

#include<bits/stdc++.h>
using namespace std;
void insertnode(vector<int> adj[], int u, int v) {
   adj[u].push_back(v);
}
void breathFirstSearch(int u, vector<int> adj[], vector<bool> &visited) {
   list<int> q;
   visited[u] = true;
   q.push_back(u);
   while(!q.empty()) {
      u = q.front();
      cout << u << " ";
      q.pop_front();
      for (int i = 0; i != adj[u].size(); ++i) {
         if (!visited[adj[u][i]]) {
            visited[adj[u][i]] = true;
            q.push_back(adj[u][i]);
         }
      }
   }
}
void BFSdisc(vector<int> adj[], int V) {
   vector<bool> visited(V, false);
   for (int u=0; u<V; u++)
   if (visited[u] == false)
   breathFirstSearch(u, adj, visited);
}
int main() {
   int V = 5;
   vector<int> adj[V];
   insertnode(adj, 0, 23);
   insertnode(adj, 0, 4);
   insertnode(adj, 1, 2);
   insertnode(adj, 1, 3);
   insertnode(adj, 1, 4);
   insertnode(adj, 2, 3);
   insertnode(adj, 3, 4);
   BFSdisc(adj, V);
   return 0;
}

出力

0 4 1 2 3