Thursday 29 November 2012

Deapth First Search (DFS) graph traversal


/*Program to create a graph and use Deapth First Search(DFS)
compiler- Turbo c++     author- Mangilal Sharma
--------------------------------------------------------*/
#include<conio.h>
#include<iostream.h>
#include<stdlib.h>

/*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;
};*/

class dfs
{
 public:
 void create();  // For creating a graph
 dfs();
 struct node *start,*p,*q;
 struct link *l,*k;
};

void dfs::create()    // Creating a graph
{
 int dat,flag=0;
 start=NULL;
 cout<<"Enter 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 "<<p->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<<"-------------------------";
 return;
}

// Deapth First Search(DFS) Traversal.
void dfs::dfs()
{
 char ch='y';
 while(ch=='y'||ch=='Y')
 {
  clrscr();
  create();
  int stack[25],top=1;
  cout<<"Deapth First Search Results";
  cout<<"---------------------------";
  p=start;
  while(p!=NULL)
  {
   p->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<<stack[top]<<"  ";
   top--;
   k=p->adj;
   while(k!=NULL)
   {
    q=k->next;
    if(q->status==0)
    {
     top++;
     stack[top]=q->data;
     q->status=1;
    }
    k=k->adj;
   }
  }
  cout<<"\n\nEnter Y/y For again enter:";
  cin>>ch;
 }return;
}
/*=========================17Nov.,2010=============================*/

No comments:

Post a Comment

You are welcome, your comment helps me to make this blog more better.