Breadth First Search: Graph Traversal Technique

Breadth First Search: Explained

Breadth first search is as widely used as Depth-first search in problem-solving.

• Concept of Breadth First Search (BFS) algorithm is used in many applications. Prim’s algorithm to find minimum spanning tree and Dijakstra’s single source shortest path algorithm uses the concept of BFS.
• For graph G = (V, E), BFS starts form some source vertex s and explores it’s all neighbors reachable from s. Any path in breadth first tree from vertex u to v corresponds to shortest path in graph G.

• This approach discovers all the vertices at distance k from the root of tree before exploring any vertex at distance k + 1.
• Figure (A) shows the order of breadth first traversal.  
• Figure (B) abd Figure (C) shows the traversing order of DFS and BFS respectively

• DFS traversal of above graph: h – d – i – f – e – b – k – f – g – c – a
• BFS traversal of above graph: a – b – c – d – e – f – g – h – i – j – k
• Breadth first search traversal explores all neighbors of current node before going to next level of neighbors.

Algorithm for Breadth First Search

The algorithm for BFS traversal is described below :

Algorithm

 BFS(v, Q)
// v is the root vertex or initial vertex
// Q is the Queue data structure to store unexplored nodes

ENQUEUE(v, Q)              // Insert v at the end of queue Q
label v as discovered

while

Q is not empty 

do

  v ← DEQUEUEU(Q)       // remove front node from queue Q
  

for

each edge from v to u 

do

if

u is not labeled as discovered 

then

      ENQUQUE(w, Q)
    

end

end

end

Complexity Analysis of Breadth First Search

• In worst case, every edge and vertex will be explored by algorithm. So time complexity of algorithm is O(|V| + |E|). Number of edged depends on how sparse the graph is? In worst case, |E| would be O(V²).
• With adjacency list representation, it requires O(|V| + |E|) space. Space complexity in case of adjacency matrix representation would be O(|V|²).

Example

DFS used stack whereas BFS uses a queue for traversing the graph. Figure 1 simulates the function of BFS. Following color conventions are used for simplicity :

• White : Undiscovered state. Initially all nodes are in undiscovered state and hence white.
• Gray : Discovered but not fully explored. When algorithm encounters node first time, it is inserted in queue and converted white to gray.
• Black : Fully explored / visited. When node v is removed from queue and all its neighbours are inserted in queue, node v is called fully explored / visited and converted gray to black.
• Let us start with arbitrary node c. Initial node c is inserted in queue labelled as Q. Node c is in queue, so it is gray and it is in discovered but not fully  explored state. Figure 1(a)
• Now, Front node c is removed from queue and labelled as visited, so it is converted from gray to black. All its neighbours are inserted in to queue. Here, g is the only neighbor of c. Node g is inserted in Q and colored gray. Figure 1(b).
• Next, the front node g is removed from queue and labelled as visited, and all its unvisited neighbours are inserted in queue. Figure 1(c).
• Node f is at the front of queue and hence it is removed from queue and labelled as visited. All its unvisited neighbours are inserted in queue (Figure 1(d).
• This process continues until Q is empty.