One of the applications of DFS is to find the number of connected components in a graph.In graph theory, a connected component of an undirected graph is a sub-graph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the super-graph.
A depth first search that begins at some particular vertex v will find the entire connected component containing v (and no more) before returning.To find all the connected components of a graph, loop through its vertices, starting a new depth first search whenever the loop reaches a vertex that has not already been included in a previously found connected component.
Another application is to find if the given graph is a tree or not.A tree is an undirected graph which is connected and does not have cycles.
Properties of a tree-
1.The tree should have only one connected component ie. it is not a disconnected graph.
2.If the graph has N vertices and N-1 edges,then it is a tree.This condition ensures that no cycles are formed.
For a graph to be a tree,both the above conditions must be satisfied.Number of components is found using the above algorithm and it should be 1.Then,the second relation must be verified.
using namespace std;
//counter counts the number of components
void dfs(int node)
color[node]=2;//marking the visited nodes
// n is the number of vertices
// m is the number of edges
//clearing the arrays and vectors
//a and b denote the starting and ending points of the edge
//maintaining the adjacency lists
//looping through the vertices
printf("Number of components is %d\n",counter);
if((m==n-1)&&(counter==1))printf("IT IS A TREE\n");
else printf("NOT A TREE\n");