Breadth First Search
AIM:
Implement Breadth First Search
Description:
In this program, an un-directed graph is created with no weights, and Breadth First Search is performed based on starting vertex.
Program:
#include<stdio.h>
#include<stdlib.h>
struct Graph
{
int v;
int e;
int adjMat[20][20];
};
struct Graph* createGraph(int v,int e)
{
int i,j;
struct Graph* g=(struct Graph*)malloc(sizeof(struct Graph));
g->v=v;
g->e=e;
for(i=0;i<v;i++)
{
for(j=0;j<v;j++)
{
g->adjMat[i][j]=0;
}
}
return g;
}
void insertEdges(struct Graph* g)
{
int i,src,dest;
printf("\n Enter Source and Destination Vertices for each edge: ");
i=0;
while(i<g->e)
{
printf("\n Edge %d : ",i+1);
printf("\n Source Vertex : ");
scanf("%d",&src);
printf(" Destination Vertex : ");
scanf("%d",&dest);
if(src>g->v||dest>g->v)
{
printf("\n Vertex does not exists! Enter Again! \n");
}
else if(g->adjMat[src][dest]>0)
{
printf("\n Edge already exists! Enter Again! \n");
}
else
{
g->adjMat[src][dest]=1;
g->adjMat[dest][src]=1;
i++;
}
}
}
void displayGraph(struct Graph* g)
{
int i,j;
printf("\n Adjacency Matrix Representation : \n");
for(i=0;i<g->v;i++)
{
printf("\n");
for(j=0;j<g->v;j++)
{
printf(" %d",g->adjMat[i][j]);
}
}
printf("\n");
}
void BFS(struct Graph* g)
{
struct Graph* FG=createGraph(g->v,g->v-1);
int i,j,k,queue[g->v],front,rear,flag,ver,start,Result[g->v];
printf("\n Enter Starting Vertex : ");
scanf("%d",&start);
if(start>=g->v)
{
printf("\n Vertex doesn't exists");
}
else
{
front=rear=0;
j=0;
queue[rear]=start;
rear++;
while(rear!=front)
{
ver=queue[front];
Result[j]=queue[front];
front++;
j++;
for(i=0;i<g->v;i++)
{
flag=0;
if(g->adjMat[ver][i]==1&&i!=ver)
{
k=front;
while(k<rear)
{
if(queue[k]==i)
{
flag=1;
break;
}
else
{
k++;
}
}
k=0;
while(k<j)
{
if(Result[k]==i)
{
flag=1;
break;
}
else
{
k++;
}
}
if(flag==0)
{
queue[rear]=i;
FG->adjMat[i][ver]=1;
FG->adjMat[ver][i]=1;
rear++;
}
}
}
}
printf("\n Final Graph : ");
displayGraph(FG);
printf("\n Breadth First Search : ");
for(i=0;i<j;i++)
{
printf(" %d ",Result[i]);
}
}
}
int main()
{
int v,e;
printf("\n Enter No. of Vertices: ");
scanf("%d",&v);
printf("\n Enter No. of Edges: ");
scanf("%d",&e);
struct Graph* g=createGraph(v,e);
insertEdges(g);
displayGraph(g);
BFS(g);
return 0;
}
OUTPUT
Enter No. of Vertices: 5
Enter No. of Edges: 7
Enter Source and Destination Vertices for each edge:
Edge 1 :
Source Vertex : 0
Destination Vertex : 1
Edge 2 :
Source Vertex : 0
Destination Vertex : 3
Edge 3 :
Source Vertex : 1
Destination Vertex : 2
Edge 4 :
Source Vertex : 1
Destination Vertex : 3
Edge 5 :
Source Vertex : 1
Destination Vertex : 4
Edge 6 :
Source Vertex : 2
Destination Vertex : 4
Edge 7 :
Source Vertex : 3
Destination Vertex : 4
Adjacency Matrix Representation :
0 1 0 1 0
1 0 1 1 1
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
Enter Starting Vertex : 2
Final Graph :
Adjacency Matrix Representation :
0 1 0 0 0
1 0 1 1 0
0 1 0 0 1
0 1 0 0 0
0 0 1 0 0
Breadth First Search : 2 1 4 0 3
--------------------------------
Process exited after 8.713 seconds with return value 0
Press any key to continue . . .
No comments:
Post a Comment