Nov
28
2008

C++ Program to create a graph and use Depth First Search(DFS)

C++ Program to create a graph and use Depth First Search(DFS).

/**************************************************************
	Author: Arun Vishnu M V
	Web: www.arunmvishnu.com
	Description: C++ Program to create a graph and use Deapth First Search(DFS)
     and Breadth First Search(BFS) Traversal.
***************************************************************/
#include
#include
#include

void create();  // For creating a graph
void dfs();  // For Deapth First Search(DFS) Traversal.
void bfs();  // For Breadth First Search(BFS) Traversal. 

struct node  // Structure for elements in the graph
{
   int data,status;
   struct node *next;
   struct link *adj;
};

struct link  // Structure for adjacency list
{
   struct node *next;
   struct link *adj;
};

struct node *start,*p,*q;
struct link *l,*k;

int main()
{
   int choice;
   clrscr();
   create();
   while(1)
   {
      cout<<"\n\n-----------------------";
      cout<<"\n1: DFS\n2: BSF\n3: Exit\nEnter your choice: ";
      cin>>choice;
      switch(choice)
      {
	 case 1:
	    dfs();
	    break;
	 case 2:
	    bfs();
	    break;
	 case 3:
	    exit(0);
	    break;
	 default:
	    cout<<"\nIncorrect choice!\nRe-enter your choice.";
	    getch();
      }
   }
   return 0;
}

void create()    // Creating a graph
{
   int dat,flag=0;
   start=NULL;
   cout<<"\nEnter the nodes in the graph(0 to end): ";
   while(1)
   {
      cin>>dat;
      if(dat==0)
	 break;
      p=new node;
      p->data=dat;
      p->status=0;
      p->next=NULL;
      p->adj=NULL;
      if(flag==0)
      {
	 start=p;
	 q=p;
	 flag++;
      }
      else
      {
	 q->next=p;
	 q=p;
      }
   }
   p=start;
   while(p!=NULL)
   {
      cout<<"Enter the links to "<data<<" (0 to end) : ";
      flag=0;
      while(1)
      {
	 cin>>dat;
	 if(dat==0)
	    break;
	 k=new link;
	 k->adj=NULL;
	 if(flag==0)
	 {
	    p->adj=k;
	    l=k;
	    flag++;
	 }
	 else
	 {
	    l->adj=k;
	    l=k;
	 }
	 q=start;
	 while(q!=NULL)
	 {
	    if(q->data==dat)
	       k->next=q;
	    q=q->next;
	 }
      }
      p=p->next;
   }
   cout<<"\n\n-------------------------";
   return;
}


// Deapth First Search(DFS) Traversal.
void bfs()
{
   int qu[20],i=1,j=0;
   p=start;
   while(p!=NULL)
   {
      p->status=0;
      p=p->next;
   }
   p=start;
   qu[0]=p->data;
   p->status=1;
   while(1)
   {
      if(qu[j]==0)
	 break;
      p=start;
      while(p!=NULL)
      {
	 if(p->data==qu[j])
	     break;
	 p=p->next;
      }
      k=p->adj;
      while(k!=NULL)
      {
	 q=k->next;
	 if(q->status==0)
	 {
	    qu[i]=q->data;
	    q->status=1;
	    qu[i+1]=0;
	    i++;
	 }
	 k=k->adj;
      }
      j++;
   }
   j=0;
   cout<<"\n\nBreadth First Search Results\n";
   cout<<"\n---------------------------\n";
   while(qu[j]!=0)
   {
      cout<status=0;
      p=p->next;
   }
   p=start;
   stack[0]=0;
   stack[top]=p->data;
   p->status=1;
   while(1)
   {
      if(stack[top]==0)
	 break;
      p=start;
      while(p!=NULL)
      {
	 if(p->data==stack[top])
	    break;
	 p=p->next;
      }
      cout<adj;
      while(k!=NULL)
      {
	 q=k->next;
	 if(q->status==0)
	 {
	    top++;
	    stack[top]=q->data;
	    q->status=1;
	 }
	 k=k->adj;
      }
   }
   getch();
   return;
}


//---------------------- END--------------------

Related Posts

Author: Arun Vishnu

11 Comments + Add Comment

  • Hello… Can u give the same program in C? i was trying to run this in C++ but get many errors. Later i changed the program in C removing the C++ syntax. It compiled well but i get segmentation fault when i execute it. I can send the file if u wish.
    Thanks in advance

  • please send me full code snippet for the C++ Program to create a graph and use Depth First Search(DFS)..and 8-puzzle problem using DFS.

    Thank you.

  • Hello… Can u give the same program in C?

  • Hi there I copied your program and try to compile it in c++ under window 7 using code block. Not even compile. Can you send me a good version? Sincerely David

  • I think few lines were missed when converted to html. I have updated the code from the original cpp file which runs without any error.

  • Thanks man,
    I wanted to brush up on concepts after a long time and your site really helped me .
    Keep up the good work and the enthusiasm.

    And what you could do is post the zip file of the source code .
    Put it in a big download link and you will find lots of other users coming back .

  • How I can get the whole code, I mean the original cpp file. Thanks

  • how i can the full code

  • How would this be implemented for example if number of rows and columns were to be input by user, a tree based search was used and basically like a NxM Puzzle (like 8puzzle etc) in c++ ?

  • Where can I find the depth first search implementation?

    Thank You

  • Can you send the whole c++ code to shone-01@live.com. Thanks

Leave a comment

Archives

Highslide for Wordpress Plugin