Contents
Breadth First Search/Traversal
C program to implement Breadth First Search(BFS). Breadth First Search is an algorithm used to search a Tree or Graph. BFS search starts from root node then traverses into next level of graph or tree, if item found it stops other wise it continues with other nodes in the same level before moving on to the next level. The algorithm can also be used for just Tree/Graph traversal, without actually searching for a value. This is what being done in the program below. The disadvantage of BFS is it requires more memory compare to Depth First Search(DFS).
The Program
| #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; | |
| } | |
| } | |
| } |
Sample Output
The graph’s matrix representation is used as input to our program. A value of 1 at [i][j] represents presence of a path from i to j. 0 represents no path.
Related Programs
To get regular updates on new C programs, you can Follow @c_program on Twitter. Or you can discuss these programs on our Facebook Page.
6 comments on “Breadth First Search (BFS) in C”
Hi Dear..
Can u provide samaple input. Please reply ASAP.
This comment has been removed by the author.
It would be better if you can use variable names that make sense. just using a, b,c n, confuses and doesnt help for what its been used.
Thanks for one’s marvelous posting! I seriously enjoyed reading it, you could be
a great author. I will be sure to bookmark your blog and will often come back down the road.
I want to encourage continue your great posts, have a nice day!
Thanks for commenting! I don’t know how a programming site helped you, but I appreciate you writing!
Why is there no base condition in recursion of bfs ?