Program of Deapth First Search Traversal ( DFS )

#include <iostream.h>
#include <conio.h>
#define MAX_NODE 50

struct node{
    int vertex;
    node *next;
};

node *adj[MAX_NODE]; //For storing Adjacency list of nodes.
int totNodes; //No. of Nodes in Graph.

////////////Stack Operation\\\\\\\\\\\\\\\\\\\\\\\\    int top=-1;
int stack[MAX_NODE];

void push(int item){
     top=top+1;
     stack[top]=item;
}

int pop(){
     int deldata=stack[top];
     top=top-1;
     return(deldata);
}

int is_stk_empty(){
     if(top==-1)
     return(1);
     else
     return(0);
}
////////////Stack Operation\\\\\\\\\\\\\\\\\\\\\\\\    
void createGraph(){
    node *newl,*last;
    int neighbours,neighbour_value;
    cout<<\"\\n\\n---Graph Creation---\\n\\n\";
    cout<<\"Enter total nodes in graph : \";
    cin>>totNodes;
    for(int i=1;i<=totNodes;i++){
        last=NULL;
        cout<<\"\\nEnter no. of nodes in the adjacency list of node \"<<i<<\"\\n\";
        cout<<\"--> That is Total Neighbours of \"<<i<<\" : \";
        cin>>neighbours;
        for(int j=1;j<=neighbours;j++){
            cout<<\"Enter neighbour #\"<<j<<\" : \";
            cin>>neighbour_value;
            newl=new node;
            newl->vertex=neighbour_value;
            newl->next=NULL;
            if(adj[i]==NULL)
                adj[i]=last=newl;
            else{
                last->next = newl;
                last = newl;
            }
        }
    }
}


void DFS_traversal(){
    node *tmp;
    int N,v,start_node,status[MAX_NODE];//status arr for maintaing status.
    const int ready=1,wait=2,processed=3; //status of node.

    cout<<\"Enter starting node : \";
    cin>>start_node;

    //step 1 : Initialize all nodes to ready state.
    for(int i=1;i<=totNodes;i++)
        status[i]=ready;

    //step 2 : push the start node in stack and change status.
    push(start_node); //Push starting node into stack.
    status[start_node]=wait; //change it status to wait state.

    //step 3 : Repeat until stack is empty.
    while(is_stk_empty()!=1){

        //step 4 : pop the node N of stack.
        //process N and change the status of N to
        //be processed state.
        N = pop(); //pop the node from stack.
        status[N]=processed; //status of N to processed.
        cout<<\"   \"<<N; //displaying processed node.

        //step 5 : push onto stack all the neighbours of N,
        //that are in ready state and change their status to
        //wait state.
        tmp = adj[N];  //for status updation.
        while(tmp!=NULL){
            v = tmp->vertex;
            if(status[v]==ready){//check status of N\'s neighbour.
                push(v); //push N\'s neighbour who are in ready state.
                status[v]=wait; //and make their status to wait state.
            }
            tmp=tmp->next;
        }
    }
}

void main(){
    clrscr();
    cout<<\"*****Depth First Search Traversal*****\\n\";
    createGraph();
    cout<<\"\\n===DFS traversal is as under===\\n\";
    DFS_traversal();
    getch();
}