CS201: Elementary Data Structures

Breadth First Search is a graph traversal technique that visits all vertices of the graph in a level order. By level, we mean that the source vertex is visited first, then all of its adjacent vertices, followed by vertices adjacent to those visited in the previous step. We use a queue for this purpose. To understand the traversal more clearly, we take an example of the below graph:

This is how the traversal must occur:

1. Visit 1
2. Queue now has 2 , 3 (in that order)
3. Visit 2
4. Queue = { 3 , 4 , 5 }
5. Visit 3
6. Queue = { 4 , 5 , 6 , 7 }
7. Visit 4
8. Queue = { 5 , 6 , 7 , 8 }
9. Visit 5
10. Queue = { 6 , 7 , 8 , 9 }
11. Visit 6
12. Queue = { 7 , 8 , 9 , 10 }
13. Visit 7
14. Queue = { 8 , 9 , 10 }
15. Visit 8
16. Queue = { 9 , 10 , 9 }
17. Visit 9
18. Queue = { 10 , 9 , 10 }
19. Visit 10
20. Queue = { 9 , 10 } Here we don't visit 9 because it is already visited, and same goes for 10.

Now that we know how to traverse, let's jump to the code:

#include<stdio.h>
int G[20][20],q[20],visited[20],n,front = 1, rear = 0 ;
void bfs(int v)
{
    int i;
    visited[v] = 1;
 for(i=1;i<=n;i++)
  if(G[v][i] && !visited[i])
   q[++rear]=i;
   if(front <= rear)
    bfs(q[front++]);
 }


int main()
{
 int v,i,j;

 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",&G[i][j]);
 printf("\n Enter the starting vertex:");
 scanf("%d",&v);
 bfs(v);
 printf("\n The nodes which are reachable are:\n");
 for(i=1;i<=n;i++)
  if(visited[i])
   printf("%d\t",i);
  else
   printf("\n %d is not reachable",i);

return 0;
}

Source: The Daily Programmer, http://www.thedailyprogrammer.com/2015/07/breadth-first-search.html
 This work is licensed under a Creative Commons Attribution 4.0 License.