Find number of connected component in a Graph (efficiently)

general
, ,
1

I want to find the number of all connected component in graph with details of component.

Graph is given in the form of edge.

edge 1 - a1 a2

edge 2 - b1 b2

…

where a1,a2,b1,b2 are vertex of graph. Please help guys.

2

learn about DFS/BFS

3

The code is shown below

//inside main if u r using vector<vector<pair<int,int> > >Graph(n);//Adjecency list representation of graph
numCC=0;
vector<int> dfs_num;
dfs_num.assign(V,DFS_WHITE) //use #define DFS_WHITE=-1;
 for(int i=0;i<V;i++){
        if(dfs_num[i]==DFS_WHITE)
         printf("Connected %d", ++numCC),dfs(i),printf("\n");
}

printf("%d",numCC);

//note dfs(i) is a procedure for depth first search

1 Like
4

Thanks man but can I get a quick solution with some explanation?

5

There are plenty of tutorials on DFS/BFS. Wikipedia has great ones too.

6

The solution is fairly straight-forward. Number of connected components means that number of separate entities in a graph. No two entities are linked together by an edge. Start traversing the graph, from any node… let’s assume it’s node 1. Colour this node with some colour 1. Go to all neighbours of that node. Colour these nodes 1.Then go again to all neighbours of these nodes, colour them too with 1. This process stops when all the nodes of that particular entity is coloured. Then it’s time to go to the second entity. For this search for the next node(we started with 1 first) which is not coloured. Do the same process for this node with colour 2(prev colour+1). This too stops when all nodes of that entity is coloured with 2. After all the nodes are coloured, this entire routine stops. The last colour number is the number of connected components. Remember that the graph has to bi-directional for all edges.

1 Like
7

Not necessarily that the edges have to be bi directional.