depth first search.cpp

depth first search is an efficient searching algorithm

#include<iostream.h>
#include<conio.h>

#define MAX 20
#define WHITE 0
#define GRAY 1
#define BLACK 2
#define NIL -1

int tim;
int adjMatrix[MAX][MAX];

struct node
{
     char name;
     int startTime;
     int endTime;
     int pi;
     int color;
};  

void getData(struct node *vertex , int n)
{
     int i=0;
     for(i=0;i<n;i++)
     {
          cin>>vertex[i].name;
          vertex[i].color=WHITE;
          vertex[i].pi = NIL;
     }
     
}

int findAdj(int *adj , int index , int n)
{
     int count =  0;
     for(int i=0;i<n;i++)
     {
          if(adjMatrix[index][i] != 0)
          {
               adj[count++] = i;
          
          }
     }
     return count;
}


void DFSvisit(struct node *vertex , int u , int n)      //u is the visited node n is no. of nodes
{
     int *adjacent , noOfAdjacent , i;
     adjacent = new int[n];
     vertex[u].color = GRAY;
     
     vertex[u].startTime=++tim;
     noOfAdjacent = findAdj(adjacent , u , n);
     
     printf("%c ",vertex[u].name);
     for(i=0;i<noOfAdjacent;i++)
           if(vertex[adjacent[i]].color == WHITE)
           {
                  vertex[adjacent[i]].pi = u;
                  DFSvisit(vertex , adjacent[i] , n);
           }
      vertex[u].color = BLACK;
      vertex[u].endTime = ++tim;
      
}

int main()
{
     int n , i,j;
     
     cout<<"\nEnter the no. of nodes : ";
     cin>>n;
     struct node *vertex;
     vertex = new node[n];
     cout<<"\nEnter the name of nodes(starting from source) : ";
     getData(vertex , n);
     cout<<"\n\nEnter the Values of the Adjacency Matrix(in 0,1) : ";
     for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        {
            printf("\nPath %c--->%c = ",vertex[i].name,vertex[j].name);
            scanf("%d",&adjMatrix[i][j]);
        }
     cout<<"DFS visit will be as follows : ";   
     for(i=0;i<n;i++)
     {
          if(vertex[i].color==WHITE)
               DFSvisit(vertex , i,n);
     }
     
     cout<<"\nFinal Result is : \n";
     for(i=0;i<n;i++)
          printf("Node : %c(%d/%d) \n",vertex[i].name , vertex[i].startTime , vertex[i].endTime);
     getch();
     return 0;
}