C++의 연결이 끊긴 그래프용 BFS

연결 해제된 그래프 하나 이상의 노드가 그래프의 끝점이 아닌, 즉 연결되지 않은 그래프입니다.

연결이 끊긴 그래프...

이제 Simple BFS는 그래프가 연결된 경우에만 적용할 수 있습니다. 즉, 그래프의 모든 정점이 그래프의 한 노드에서 액세스할 수 있습니다. 위의 연결이 끊긴 그래프에서는 몇 가지 법칙에 접근할 수 없어 기술이 불가능하므로 다음과 같이 변경된 프로그램이 연결이 끊긴 그래프에서 너비 우선 탐색을 수행하는 것이 더 좋습니다.

예시

#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