Program
#include <stdio.h>
#include <conio.h>
void BFS(int[20][20], int, int[20], int);
void main()
{
int n, a[20][20], i, j, visited[20], source;
printf("****************************************************************");
printf("\n****************************************************************");
printf("\n** Program for Breadth First Search in C **");
printf("\n** Created by Sheetal Garg **");
printf("\n** Assistant Professor **");
printf("\n** Phone No:9467863365 **");
printf("\n****************************************************************");
printf("\n****************************************************************");
printf("\nEnter the number of vertices:");
scanf("%d", &n);
printf("\nEnter the adjacency matrix:\n");
for (i = 1; i <= n; i++)
{
for (j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
}
for (i = 1; i <= n; i++)
visited[i] = 0;
printf("\nEnter the source node:");
scanf("%d", &source);
visited = 1;
BFS(a, source, visited, n);
for (i = 1; i <= n; i++)
{
if (visited[i] != 0)
printf("\n Node %d is reachable", i);
else
printf("\n Node %d is not reachable", i);
}
getch();
}
void BFS(int a[20][20], int source, int visited[20], int n)
{
int queue[20], f, r, u, v;
f = 0;
r = -1;
queue[++r] = source;
while (f <= r)
{
u = queue[f++];
for (v = 1; v <= n; v++)
{
if (a[u][v] == 1 && visited[v] == 0)
{
queue[++r] = v;
visited[v] = 1;
}
} // for v
} // while
}
Output 1
**************************************************************** **************************************************************** ** Program for Breadth First Search in C ** ** Created by Sheetal Garg ** ** Assistant Professor ** ** Phone No:9467863365 ** **************************************************************** **************************************************************** Enter the number of vertices:4 Enter the adjacency matrix: 0 1 0 0 1 0 1 1 0 0 0 0 1 1 0 0 Enter the source node:2 Node 1 is reachable Node 2 is reachable Node 3 is reachable Node 4 is reachable