Data Structure and Algorithm

/****************************************
APPLICATION : Breadth First Search (BFS)
CODED BY    : Ankit Pokhrel
COMPILED ON : Borland C++ Ver 5.02
DATE     : 2010 - October - 13
****************************************/

#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 BFS(Node *n,char from,char to) //Breadth First Search
{
char Queue[30],Origin[30];
int Front = -1,Rear = -1,k = -1,flag;
char ch = from;
Node *temp,*tmp;
Queue[++Rear] = from;
++Front;
Origin[++k] = '#';
while(ch != to)
{
  temp = n;
  flag = false; //suppose that there is no path between two nodes
  while(temp != NULL)
  {
   if(temp -> data == ch)
    {
     flag = true; //there is a path
     temp -> status = true; //update status
     break;
    }
   temp = temp -> next;
  }

  if(flag == false)
    break;

  Adjacent *a = temp -> adj; //goto Adjacent node
  while(a -> adj != NULL)
  {
   tmp = a -> next;
   if(tmp -> status == false)
    {
     Queue[++Rear] = tmp -> data; //Add to Queue
     Origin[++k] = temp -> data; //Save Origin
     tmp -> status = true; //update status
    }
   a = a -> adj;
  }
  ch = Queue[++Front];
}

//Backtrack and Print
if(flag != false)
{
  ch = to;
  flag = false;
  for(int j = (k+1);j > 1;j--)
   {
    if(flag == true)
     ch = Origin[j];
    char c = Origin[j - 1];

    if(c != ch)
    {
     temp = n;
     while(temp -> data != c)
      temp = temp -> next;
     Adjacent *a = temp -> adj;
     while(a -> adj != NULL)
      {
       flag = false;
       tmp = a -> next;
       if(tmp -> data == ch)
       {
        cout << tmp -> data << " <- ";
        flag = true;
        break;
       }
       a = a -> adj;
      }
    }
   }
  cout << from;
}

else
  cout << "There is no path between " << from << " to " << to;
}

int main()
{
int m;
char c,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 Minimum Path From : ";
cin >> c;
cout << "To : ";
cin >> ch;
cout << " \nThe Minimum Path from (" << c << " to " << ch << ") : ";
BFS(nd,c,ch);
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 Minimum Path From : A
To : J

The Minimum Path from (A to J) : J <- E <- G <- B <- A

Download Original File

Breadth First Search (BFS)