|
This post is completed by 1 user
|
Add to List |
393. Count number of subgraphs in a given graph
Objective: Given a Graph, write a program to count all the subgraphs.
Example:
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.
Output:
Number of Subgraphs: 4 Number of Subgraphs: 3 Number of Subgraphs: 2 Number of Subgraphs: 1