BFS (Breadth first search) on Graph

Algorithm

• Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we've visited it, process v, and 
• then visit i.e. mark the vertex as visited and process all of v's neighbors. 
• Now that we've visited and processed all of v's neighbors, 
• we need to visit and process all of v's neighbors neighbors

Pseudocode

BFS(graph G, vertex s)
[all nodes initially unexplored]
-mark s as explored
let Q = queue data structure, initialized with s
while (Q not empty)
     remove the first node of Q, call it v
     for each edge (v, w):
          if w is unexplored
               mark w as explored
               add w to Q (at the end)

We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we're at node v and at node w).

Example
Consider the graph

Let s be the starting vertex.
Layer 0 is node s, then a and b are layer 1. So, when layer 0 is processed, we add layer 1 to queue.
Layer n+1 gets added to the queue when we process layer n.

Time Complexity: 

Adjacency list implementation of graph - O(|V|+|E|) OR O(n+m) where |V| and |E| is number of vertices and edges for adjacency list representation of graph.
Running time for adjacency matrix - O(|V|²) OR O(n²)

where V - number of vertices and E number of edges which can be reached from the starting vertex. Also this is time complexity for adjacency list implementation.

Applications of BFS

• Application 1- Shortest paths - Dijkstra's algorithm
• Application 2 - Undirected connectivity