Skip to content

Instantly share code, notes, and snippets.

@snadahalli
Created September 11, 2017 13:21
Show Gist options
  • Star 5 You must be signed in to star a gist
  • Fork 1 You must be signed in to fork a gist
  • Save snadahalli/c6abe7d882ad7e8cbf148190183f4633 to your computer and use it in GitHub Desktop.
Save snadahalli/c6abe7d882ad7e8cbf148190183f4633 to your computer and use it in GitHub Desktop.
Breadth First Search(BFS) Program in C.
#include<stdio.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;
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. Not all nodes are reachable");
break;
}
}
}
@Alishaaliee
Copy link

this code is taking input in loop.

@bhavesh0908
Copy link

can we give the starting vertex as default

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment