December 02, 2019
Amitraj
2. Breadth First Search
-> Breadth first search is used for traversing a finite graph.
-> It visits the neighbor vertices before visiting the child vertices.
-> BFS uses a queue for search process and gets the next vertex to start a search when a dead end occurs in any iteration.
-> It traverses a graph in a breadth-ward motion.
-> It is used to find the shortest path from one vertex to another.
-> The main purpose of BFS is to traverse the graph as close as possible to the root node.
-> BFS is a different approach for traversing the graph nodes.
/* C program to implement BFS (Breadth first search) */
#include<stdio.h>
int q[20],front=-1,rear=-1,a[20][20],vis[20];
int delete();
void add(int item);
void bfs(int s,int n);
void main()
{
int n,i,s,j;
printf("Enter number of Vertices:");
scanf("%d",&n);
printf("Enter adjacency matrix of the graph:");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
for(i=1;i<=n;i++)
vis[i]=0;
printf("ENTER THE SOURCE VERTEX :");
scanf("%d",&s);
bfs(s,n);
}
void bfs(int s,int n)
{
int p,i;
add(s);
vis[s]=1;
p=delete();
if(p!=0)
printf(" %d",p);
while(p!=0)
{
for(i=1;i<=n;i++)
if((a[p][i]!=0)&&(vis[i]==0))
{
add(i);
vis[i]=1;
}
p=delete();
if(p!=0)
printf(" %d ",p);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
bfs(i,n);
}
void add(int item)
{
if(rear==19)
printf("QUEUE FULL");
else
{
if(rear==-1)
{
q[++rear]=item;
front++;
}
else
q[++rear]=item;
}
}
int delete()
{
int k;
if((front>rear)||(front==-1))
return 0;
else
{
k=q[front++];
return(k);
}
}
OUTPUT:
Enter number of Vertices:5
Enter adjacency matrix of the graph:
0 1 0 0 0
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0
ENTER THE SOURCE VERTEX :1
1 2 3 4 5
