# Finding connected components in a graph using BFS

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?

• Suggestion: Once you completely color one component, pick an uncolored node and a new "color" (component ID) to identify the next component. Commented Mar 19, 2018 at 20:59
• @Joffan thanks! But how do I know which of the colors I've already used? I think colors are tricky..given that components can be endless. So if I use numbers instead, how do I know that I've already used a given number?
– Lola
Commented Mar 19, 2018 at 21:03
• Start at $1$ and increment? Or, presumably your vertices have some ID, so name the component for (eg.) the lowest-numbered vertex contained (determined during BFS if necessary). Commented Mar 19, 2018 at 21:32
• @Lola is actually a very funny name (Google it for india region). XD Commented May 28, 2021 at 18:39

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+1


The 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.

• Brilliant answer! Thank you very much!!
– Lola
Commented Mar 20, 2018 at 10:32
• Hey, I forgot to ask. Can I also use DFS for this type of question?
– Lola
Commented Mar 21, 2018 at 9:38
• Yes, it's the same concept. Call DFS once for each unvisited vertex so far, with a parameter passed to keep track of the connected component associated with vertices reachable from the given start vertex. Ultimately DFS is called once for each connected component, and each time it is called again from a new start vertex the componentID increments. Commented Mar 21, 2018 at 18:14

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;

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;