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

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: