# 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
^{2}). - With adjacency list representation, it requires O(|V| + |E|) space. Space complexity in case of adjacency matrix representation would be O(|V|
^{2}).

## 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.