Count number of subgraphs in a given graph

Objective: Given a Graph, write a program to count all the subgraphs.


Approach: Use Depth-First Search

Start the DFS from any random vertex. Once DFS is completed check if all the vertices are visited. If the graph is completed connected then after first DFS all the vertices will be marked as visited. If the graph is disconnected then start another DFS from any vertex which is still not visited after the first round of DFS and check again if all the vertices are visited. Repeat the above process until all the vertices are visited. Keep counting the no of DFS calls. This will be our answer to the number of subgraphs.

Complete Code:


Number of Subgraphs: 4
Number of Subgraphs: 3
Number of Subgraphs: 2
Number of Subgraphs: 1

Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.

You may also like...

%d bloggers like this: