Breath First Search

Idea

Breath First Search expands the shallowest node in the tree first. BFS mostly uses a adjacent list. It is complete, optimal for unit-cost operators and has time and space complexity of O(V+E). If you don't know the big O notation please read the big O notation article first.

Pseudo - code

Here we are calculating the shortest path between beg and end, we suppose there are less then one million edges and it is not a weighted graph :

BFS (adj,beg,end){
    initialize Q = {{beg,0}} // a queue with {node,sum}
    initialize a vu table with 1000000 as initial value
    while (Q not empty){
        f = top element of Q
        dequeue(Q)
        for all neighbors in adj {
            if vu[neighbors] > f.sum {
                vu[neighbors] = f.sum
                add {neighbors,f.sum+1} to Q
            }
        }
    }
    return vu[end]
}

C++ code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct vertex{
        int node,sum;
};

int n,m;

inline int BFS(vector<vector>& adj,int beg,int end){
 queue q;
 q.emplace(beg,0);
 vector vu(n,1000000);
 while (!q.empty()){
  auto f = q.front();
  q.pop();
  for (int& neighbor:adj[f.node]){
   if (vu[neighbor] > f.sum+1){
    vu[neighbor] = f.sum+1;
    q.emplace(neighbor,f.sum+1);
   }
  }
 }
 return vu[end];
}

int main(){
 ios::sync_with_stdio(0);
 cin.tie(0);
 // initiation
 // n the number of vertices, m the number of edges
 cin >> n >> m;
 vector<vector> adj(n);
 for (int i=0; i<m; ++i){
                int a,b; // directed graph a to b
                cin >> a >> b;
  adj[a].emplace_back(b);
 }
 BFS(adj,0,n-1);
 return 0;
}

Applications

Here is a small list of the applications of BFS. BFS can be used for :

• Shortest path and minimum spanning tree
• GPS Navigation systems
• Ford - Fulkerson algorith,
• To test if a graph is bipartite
• Path Finding
• ......