Applications of DFS

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.

Algorithm-

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.

Algorithm-

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.

Code-


#include<stdio.h>
#include<vector>
using namespace std;

  vector<int>arr[10005];
  int n,a,b,j=0,m;
  int color[100005];

//counter counts the number of components
 
  int counter;


void dfs(int node)
{
     color[node]=2;//marking the visited nodes

     for(int i=0;i<arr[node].size();++i)
     {
                   
       if(color[arr[node][i]]==0)
     {
         dfs(arr[node][i]);
        }
     }             
}

int main()
{
   int t,p;
   int i;
   counter=0;
   p=1;
   j=0;

// n is the number of vertices
// m is the number of edges

    scanf("%d %d",&n,&m);

//clearing the arrays and vectors

    for(i=0;i<n;i++)
    arr[i].clear();

    for(i=0;i<n;++i){
                       color[i]=0;
                       }

     while(j<m){

//a and b denote the starting and ending points of the edge

               scanf("%d %d",&a,&b);

//maintaining the adjacency lists

               arr[a-1].push_back(b-1);
               arr[b-1].push_back(a-1);
               j++;

               }
//looping through the vertices

               for(i=0;i<n;++i)
              {
                  if(color[i]==0)
                 {
                    dfs(i);
                    counter++;
                 }
              }

     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");

                  
   return 0;
}

Leave a Reply

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

*

* Copy This Password *

* Type Or Paste Password Here *

43,751 Spam Comments Blocked so far by Spam Free Wordpress

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>