C Program to implement Breadth First Search (BFS) traversal in a graph using adjacency matrix representation
C Program To Implement Breadth First Search (BFS) Traversal In A Graph Using Adjacency Matrix Representation
Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a ‘search key’ and explores the neighbor nodes first, before moving to the next level neighbors.
Source: Wikipedia
Program in C for Breadth First Search
#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("%dt",i); else printf("n Bfs is not possible"); getch(); }
Try to put comments in the code. It would b better.