Data Structure and Algorithm

/****************************************
APPLICATION : Depth First Search (DFS)
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE     : 2010 - October - 12
****************************************/

#include "iostream.h"
#include "conio.h"

struct Node //Structure to represent a Node or Vertices of a Graph
{
int status;
char data;
struct Node *next,*head; //Pointers to next node and Start
struct Adjacent *adj; //Pointer to Adjacent node
};

struct Adjacent //Structure to represent Adjacent node of a Graph
{
struct Node *next;
struct Adjacent *adj; //Pointer for next Adjacent
};

Node *New,*top; //Global Variables for New node and Pointer to Top
void create()
{
New = new Node; //Create a node
New -> status = false;
New -> next = NULL;
New -> adj = NULL;
}

void CreateVertices(Node *&n,char Item) //Function to Create a Vertices of a Graph
{
if(n == NULL) //if first node
  {
   n = new Node; //Create a node
   n -> data = Item; //Insert Data
   n -> status = false;
   n -> next = NULL;
   n -> adj = NULL;
   n -> head = n; //Initialize head
   top = n; //Update top
   return;
  }

create(); //Create a node
New -> data = Item; //Insert Item
top -> next = New; //Assign new node to next of top
top = New; //Update top
}

void LinkVertices(Node *&n)
{
Adjacent *a,*ptr;
cout << "\nEnter Link for each Vertices (0 as Last Input): ";
Node *temp = n -> head,*tmp;
while(temp != NULL) //Until last
{
  cout << "\nEnter Adjacents of " << temp -> data << " : ";
  int flag = 0;
  char ch;
  do
   {
    cin >> ch; //Scan Adjacent
    a = new Adjacent; //Create an Adjacent
    a -> adj = NULL;
    a -> next = NULL;
    if(flag == 0) //if first Adjacent
     {
      temp -> adj = a;
      ptr = a;
      flag++; //Increase flag
     }

    else
     {
      ptr -> adj = a;
      ptr = a;
     }

   tmp = n -> head; //from start
   while(tmp != NULL) //Until end
    {
     if(tmp -> data == ch) //if node found
      a -> next = tmp; //Link adjacent
     tmp = tmp -> next;
    }
   }while(ch != '0');
   temp = temp -> next;
  }
}

void DFS(Node *n,char Item)
{
int top = -1;
char stack[30]; //Create a Stack
stack[++top] = Item; //Push starting Item
cout << Item << ' ';
Node *temp,*tmp;
char ch = Item;

while(top >= 0) //until stack is empty
{
  temp = n;
  while(temp -> data != ch) //goto starting node
   temp = temp -> next;
  temp -> status = true; //update status

  Adjacent *a = temp -> adj;
  while(a -> adj != NULL)
   {
    tmp = a -> next;
    if(tmp -> status == false)
     {
      stack[++top] = tmp -> data; //save adjacents to stack
      tmp -> status = true; //update status
     }
    a = a -> adj; //goto next adjacent
   }

  ch = stack[top];
  if(top != 0)
   cout << stack[top] << ' '; //output top of stack
  --top;
}
}

int main()
{
int m;
char ch;
Node *nd = NULL;
cout << "How Many Vertices? "; //Number of Nodes on a Graph
cin >> m;

cout << "\nEnter Vertices Name : "; //Input the name of Vertices
for(int i = 0;i < m;i++)
  {
   cin >> ch;
   CreateVertices(nd,ch); //Create Vertices of a Graph
  }

LinkVertices(nd); //Link the Vertices of a Graph
cout << "\nFind nodes reachable from : ";
cin >> ch;
cout << "\nThe nodes reachable from " << ch << " : ";
DFS(nd,ch); //Depth First Traversal
getch();
}

OUTPUT

How Many Vertices? 9

Enter Vertices Name : A B C D E F G J K

Enter Link for each Vertices (0 as Last Input):
Enter Adjacents of A : F C B 0

Enter Adjacents of B : G C 0

Enter Adjacents of C : F 0

Enter Adjacents of D : C 0

Enter Adjacents of E : D C J 0

Enter Adjacents of F : D 0

Enter Adjacents of G : C E 0

Enter Adjacents of J : D K 0

Enter Adjacents of K : E G 0

Find node reachable from : J

The nodes reachable from J : J K G C F E D

Download Original File

Depth First Search (DFS).cpp