Logo 
Search:

C++ Programming Articles

Submit Article
Home » Articles » C++ Programming » Data File StructureRSS Feeds

Program of Deapth First Search Traversal ( DFS )

Posted By: Easy Tutor     Category: C++ Programming     Views: 33461

Write a program of Deapth First Search Traversal ( DFS ).

Code for Program of Deapth First Search Traversal ( DFS ) in C++ Programming

#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);
     elsereturn(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.constint 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();
}
  
Share: 


Didn't find what you were looking for? Find more on Program of Deapth First Search Traversal ( DFS ) Or get search suggestion and latest updates.

Easy Tutor
Easy Tutor author of Program of Deapth First Search Traversal ( DFS ) is from United States. Easy Tutor says

Hello Friends,

I am Free Lance Tutor, who helped student in completing their homework.

I have 4 Years of hands on experience on helping student in completing their homework. I also guide them in doing their final year projects.

I have share many programs on this website for everyone to use freely, if you need further assistance, than please contact me on easytutor.2ya [at the rate] gmail [dot] com

I have special discount scheme for providing tutor services. I am providing tutor service to students from various contries, currently most of my students are from United States, India, Australia, Pakistan, Germany, UK and Canada.

I am also here to expand my technical network to receive more opportunity in my career, make friends to help them in resolving their technical problem, learn and share my knowledge, If you like to be my friend, Please send me friend request.

Thanks,
Happy Programming :)

 
View All Articles

 
Please enter your Comment

  • Comment should be atleast 30 Characters.
  • Please put code inside [Code] your code [/Code].

 
Tarek Amin from Bangladesh Comment on: Jun 30
baaler code diso hawer pola

View All Comments