Write a program in C language that will accept a Graph as input and will perform a Breadth First Search on it. Make necessary assumptions.
Answers
Answer:
The program is written in the explanation section.
Explanation:
#include<stdio.h>
int M[30][30], p[30], visited[20], n, i, j, f = 0, r = -1;
void bfs(int v)
{
for(i = 1; i <=n; i++)
{
if(M[v][i] && !visited[i])
p[++r] = i;
if(f <= r)
{
visited[p[f]] = 1;
bfs(p[f++]);
}
}
}
int main()
{
int v;
printf("\n Enter the number of vertices:");
scanf("%d", &n);
for(i=1; i <= n; i++)
{
p[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", &M[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 all nodes are reachable");
break;
}
}
}