I'd like to know how do I change the known BFS algorithm in order to find all of the connected components of a given graph. The original algorithm stops whenever we've colored an entire component in black, but how do I change it in order for it to run through all of the components? And how do I distinguish between one component to the other?
$\endgroup$ 42 Answers
$\begingroup$Use an integer to keep track of the "colors" that identify each component, as @Joffan mentioned. Start BFS at a vertex $v$. When it finishes, all vertices that are reachable from $v$ are colored (i.e., labeled with a number). Loop through all vertices which are still unlabeled and call BFS on those unlabeled vertices to find other components.
Below is some pseudo-code which initializes all vertices with an unexplored label (an integer 0). It keeps a counter, $componentID$, which vertices are labeled with as they are explored. When a connected component is finished being explored (meaning that the standard BFS has finished), the counter increments. BFS is only called on vertices which belong to a component that has not been explored yet.
// input: graph G
// output: labeling of edges and partition of the vertices of G
LabelAllConnectedComponents(G): // initialize all vertices and edges as unexplored (label is 0) for all u ∈ G.vertices() setLabel(u, UNEXPLORED) for all e ∈ G.edges() setLabel(e, UNEXPLORED) // call BFS on every unlabeled vertex, which results in // calling BFS once for each connected component componentID = 1 for all v ∈ G.vertices() if getLabel(v) == 0: BFS(G, v, componentID++)
// standard breadth-first-search algorithm that works on one component
BFS(G, s, componentID): L[0] = new empty sequence insert vertex s at the end of L[0] setLabel(s, componentID) i = 0 while L[i] is not empty: L[i+1] = new empty sequence for all v ∈ L[i].elements() for all e ∈ G.incidentEdges(v) if getLabel(e) == UNEXPLORED w ← opposite(v,e) if getLabel(w) == UNEXPLORED setLabel(e, DISCOVERY) setLabel(w, componentID) L[i+1].insertLast(w) else setLabel(e, CROSS) i = i+1The total running time is $O(|V| + |E|)$ since each edge and vertex is labeled exactly twice - once to initialize and again when it's visited.
$\endgroup$ 3 $\begingroup$Recently I am started with competitive programming so written the code for finding the number of connected components in the un-directed graph. Using BFS.
I have implemented using the adjacency list representation of the graph. The Time complexity of the program is (V + E) same as the complexity of the BFS.
You can maintain the visited array to go through all the connected components of the graph.
Here is my code in C++.
/*
Finding the number of non-connected components in the graph
*/
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
void addEdge(vector<int> vec[],int source,int destination){ vec[source].pb(destination); vec[destination].pb(source);
}
void BFSUtil(vector<bool> &visited ,vector<int> vec[],int i){ list<int> queue; visited[i] = true; queue.pb(i); vector<int> :: iterator it; if(vec[i].size()==0){ cout<<"vec["<<i<<"].size(): "<<vec[i].size()<<endl; return; } while(!queue.empty()){ i = queue.front(); cout<<i<<" "; queue.pop_front(); for(it = vec[i].begin(); it!= vec[i].end(); it++){ if(visited[*it] == false){ queue.pb(*it); visited[*it] = true; } } }
}
void BFS(vector<int> vec[],int V){ vector<bool> visited(V,false); int total_disconnected_components = 0; for(int i=0; i<V; i++){ if(visited[i] == false){ BFSUtil(visited,vec,i); total_disconnected_components++; } } cout<<endl; cout<<total_disconnected_components<<endl;
}
int main(){ int t; cin>>t; while(t--){ int v; cin>>v; vector<int> graph[v]; int e; cin>>e; for(int i=0; i<e; i++){ int source,destination; cin>>source>>destination; addEdge(graph,source,destination); } BFS(graph,v); } return 0;
}Please let me know if any further information needed.
Thank you
Novice in competitive programming
$\endgroup$
