Aim:
To implement Breadth First Search
Description:
Breadth First Search(BFS) :BFS algorithm begins at root node & visits all the
neighbouring nodes then for each of these nearest nodes it visits their un visited neighbour
nodes . This process terminates when all nodes visited.
Algorithm:
// A breadth first search of G is carried out beginning
//at vertex v. For any node i visited[i]=1 if i has
//already been visited. The Graph G and array visited[]
//are global; visited[] is initialized to zero.
{
u:=v; //q is a queue of unexplored vertices.
visited[v]:=1;
repeat
{
for all vertices w adjacent from u do
{
if(visited[w] = 0) then
{
Add w to q; //w is unexplored
visited[w]:=1 ;
}
}
if q is empty then return //no unexplored vertex
Delete u from q; //Get first unexplored vertex.
}until(false);
}
Source Code:
#include<stdio.h>
#include<conio.h>
#define max 10
int n,adj[max][max],visited[max];
void bfs();
void readmatrix();
main()
{
}
int source;
clrscr();
printf("Enter the source node:");
scanf("%d",&source);
readmatrix();
bfs(source);
getch();
void readmatrix()
{
int i,j;
printf("Enter number of nodes:");
scanf("%d",&n);
printf("Enter adjacency matrix\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
scanf("%d",&adj[i][j]);
for(i=1;i<=n;i++)
visited[i]=0;
}
void bfs(int source)
{
int queue[max];
int i,front,rear,root;
printf("The Order is\n");
front=rear=0;
visited[source]=1;
queue[rear++]=source;
printf("%d ",source);
while(front!=rear)
{
root=queue[front];
for(i=1;i<=n;i++)
if(adj[root][i] && ! visited[i])
{
visited[i]=1;
queue[rear++]=i;
printf("%d ",i);
}
front++;
}
}
OutPut:
Enter the Source node:1
Enter number of nodes : 6
Enter Adjacency matrix:
0 0 1 0 1 1
0 0 1 0 1 0
1 1 0 1 1 1
0 0 1 0 0 1
1 1 1 0 0 0
1 0 1 1 0 0
The order is
1 3 5 6 2 4
