Breadth First Search (BFS) Algorithm

Description: -

BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.

• In this technique we start from a given vertex v and then mark it as visited (but not completely explored).

• A vertex is said to be explored when all the vertices adjacent to it are visited.

• All vertices adjacent to v are visited next, these are new unexplored vertices.

• The vertex v is now completely explored.

• The newly visited vertices which are not completely explored are put at the end of a queue.

• The first vertex of this queue is explored next.

• Exploration continues until no unexplored vertices are left.

For example: BFS of this graph will be 1, 2, 3, 4, 5, 6, 7

Algorithm: -

BFS(v) {
 u = v;
 visited[v] = true;
 // visited is an array of vertices visited so far
 // all elements are 0 initially
 do {
  for all vertices w adjacent to u do {
   if (!visited[w]) {
    add w to q;
    // q is the queue of unexplored vertices
    visited[w] = true;
   }
  }
  if (q empty) return;
  u = extract front element of q;
 }while (true);
}

Program: -

#include<stdio.h>
int graph[20][20]={0},visited[20]={0},n;
int q[20],r=-1,f=-1;
//this code is written by Monish Kumar Bairagi
void NQ(int x){
 if(f==-1 || f<r){
  r=0; f=-1;
 }
 q[++f]=x;
}

int DQ(){
 if(f==-1)
  return -1;
 return q[r++];
}

void bfs(int v){
 int i;
 NQ(v);
 visited[v]=1;
 do{
  v = DQ();
  printf("%d ",v);
  for(i=1;i<=n;i++){
   if(graph[v][i]==1 && visited[i]==0){
    NQ(i);
    visited[i]=1;
   }
  }
 } 
 while( !(f<r || f==-1) );
}
//this code is written by Monish Kumar Bairagi
int main()
{
 int m,i,j,k;
 printf("Enter total no of vertices: "); scanf("%d",&n);
 printf("Enter total no of Edges: "); scanf("%d",&m);
 printf("Enter connected vertices:-\n");
 for(k=0;k<m;k++){
  printf("Enter U V: "); scanf("%d%d",&i,&j);
  graph[i][j]=1; graph[j][i]=1;
 }
 printf("Enter Starting vertex: "); scanf("%d",&k);
 printf("The BFS Solution of the Graph will be: ");
 bfs(k); printf("\n");
 return 0;
}

Output: -

Enter total no of vertices: 8
Enter total no of Edges: 10
Enter connected vertices:-
Enter U V: 1 2
Enter U V: 1 3
Enter U V: 2 4
Enter U V: 2 5
Enter U V: 3 6
Enter U V: 3 7
Enter U V: 4 8
Enter U V: 5 8
Enter U V: 6 8
Enter U V: 7 8
Enter Starting vertex: 1
The BFS Solution of the Graph will be: 1 2 3 4 5 6 7 8

Time-Complexity: -

O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.