#include<iostream>
#define SIZE 12
using namespace std;
class Queu
{
public:
Queu();
int isempty();
void insert(int node);
int remove();
void display();
private:
int front;
int rear;
int* queue;
};
Queu :: Queu()
{
queue = new int[SIZE];
front = 0 ;
rear = 0 ;
}
void Queu :: insert(int node)
{
if( (front == 1) && (rear == 11) )
{
cout << "Overflow" <<endl;
}
else if(front == 0)
{
queue[++front] = node;
rear++;
}
else
{
queue[++rear] = node;
}
}
int Queu :: remove()
{
int item = 0;
if(front == 0 )
{
cout << "underflow" <<endl;
}
else if(front == rear )
{
item = queue[rear];
front = 0 ;
rear = 0;
return item;
}
else
{
item = queue[front++];
return item;
}
}
int Queu :: isempty()
{
if(front == 0)
{
return 0;
}
else
{
return 1;
}
}
void Queu :: display()
{
cout<<"Queue is ";
for(int i = front ; i <= rear ; i++)
{
cout<<queue[front]<<" ";
}
}
class Bfs
{
public:
Bfs();
void insert();
void search();
void initialize();
private:
int vertices;
int* status;
int** cost;
int edges;
int* pvisit; // used to store the parent of current processed node
};
Bfs :: Bfs ()
{
vertices = 0 ;
edges = 0 ;
status = new int[SIZE];
pvisit = new int [SIZE];
cost = new int*[SIZE];
initialize();
}
void Bfs :: initialize()
{
for(int i = 0 ; i < SIZE ; i ++)
{
cost[i] = new int [SIZE];
status[i] = 0 ;
pvisit[i] = 0 ;
}
}
void Bfs :: insert()
{
cout << "Enter Number of Vertices" << endl;
cin >> vertices;
cout << "Enter number of edges" << endl;
cin >> edges;
cout << "Enter the Edge " <<endl;
int i = 0 , j = 0 ;
for(int k = 0 ; k < edges ; k++)
{
cin>>i>>j;
cost[i][j] = 1;
}
}
void Bfs :: search()
{
Queu Q;
int v1 = 0 , v2 = 0 ;
cout << "Enter the initial vertex" << endl;
cin >> v1;
cout<< "Enter the Final vertex " << endl;
cin >> v2;
Q.insert(v1);
pvisit[v1] = v1;
status[v1] = 1 ;
int flag = 0;
while(Q.isempty())
{
v1 = Q.remove();
status[v1] = 2;
if(flag == 0 )
for(int i = 1 ; i <= vertices; i ++)
{
if( (cost[v1][i] == 1 ) && (status[i] == 0) )
{
Q.insert(i);
pvisit[i] = v1;
status[i] = 1 ;
if( i == v2)
{
flag = 1;
break;
}
}
}
else
break;
}
cout << v2 << " " ;
while(v2 != pvisit[v2])
{
cout << pvisit[v2] <<" " ;
v2 = pvisit[v2];
}
}
int main()
{
Bfs obj;
obj.initialize();
obj.insert();
obj.search();
cin.get();
cin.get();
return 0;
}
BY: SAURABH BHATIA
No comments:
Post a Comment