Objective: C program to implement graph traversal using Breadth First Search
Concept: BFS (Breadth First Search) is an algorithm used to search the Tree or Graph. BFS search starts from root node then traversal into next level of graph or tree and continues, if item found it stops otherwise it continues. The disadvantage of BFS is it requires more memory compare to Depth First Search (DFS).
Time Complexities:Let T(n,e) and S(n,e) be the maximum time and maximum additional space taken by algorithm BFS on any graph G with n vertices and e edges. T(n, e) = Θ(n + e) and S(n, e) = Θ(n) if G is represented by its adjacency lists. If G is represented by its adjacency matrix, then T(n, e) =Θ(n²) and S(n ,e) = Θ(n).
#include<stdio.h>
#include<conio.h>
int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
void bfs(int v)
{
for (i=1;i<=n;i++)
if(a[v][i] && !visited[i])
q[++r]=i;
if(f<=r)
{
visited[q[f]]=1;
bfs(q[f++]);
}
}
void main()
{
int v;
clrscr();
printf("\n Enter the number of vertices:");
scanf("%d",&n);
for (i=1;i<=n;i++)
{
q[i]=0;
visited[i]=0;
}
printf("\n Enter graph data in matrix form:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:");
scanf("%d",&v); bfs(v);
printf("\n The node which are reachable are:\n");
for (i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i);
else printf("\n Bfs is not possible");
getch();
}
