**Breadth First Search (BFS)** is a graph traversal algorithm that is used to traverse all the vertices of a graph in a breadthward motion. In other words, it starts the graph traversal from root node and explores all the neighboring nodes first instead of going deep.

### Example of Breadth First Traversal for a Graph

Breadth First Traversal is used to traverse all the vertices of a graph. Using this algorithm, neighboring nodes are traversed first.

Below is the example of BFS Traversal with input- output constraint and the solution for the example.

#### Input and Output of the Example

Given the undirected, connected and unweighted graph **G**, and the task is used to traverse all the vertices of a graph using BFS Traversal starting from 0.

**Output**:

Breadth First Traversal from vertex 0 is0 1 3 2.

#### Stepwise Solution of the Breadth First Traversal Example

1. Given the undirected, connected and unweighted graph **G**. Create a set **Visited** which is used to track on visited vertices and create queue **Neighbor** to store neighbor vertices.

2. Start from vertex 0, put the current vertex **(0)** in Visited list and put all its adjacent vertices **( 1, 3, 2 ) **in the stack.

Visited: | 0 |

NeighBour: | 1 | 3 | 2 |

3. Now visit next unvisited vertex from the front of **NeighBour**, put the current vertex **(1)** in Visited list. There is no new neighbour.

Visited: | 0 | 1 |

NeighBour: | 3 | 2 |

4. Similarly, visit next unvisited vertex from the front of **NeighBour**, put the current vertex **(3)** in Visited list. There is also no new neighbour.

Visited: | 0 | 1 | 3 |

NeighBour: | 2 |

5. Similarly, visit next unvisited vertex from the front of **NeighBour**, put the current vertex **(2)** in Visited list. There is also no new neighbour.

Visited: | 0 | 1 | 3 | 2 |

NeighBour: |

6. Since **NeighBour** is empty, stop the traversal. Thus the traversal is : **0 1 3 2.**

### Pseudocode for Breadth First Traversal for a Graph

Here’s pseudocode to traverse all the vertices of a graph using BFS Traversal.

Breadth_First_Traversal(G, root): Q <- queue root is visited Q.enqueue(root) while Q is not empty do v <- Q.dequeue() if v is the target then return v for all edges from v to w in G.adjacentEdges(v) do if w is not visited then w is visited w.parent <- v Q.enqueue(w)

### Implementation of Breadth First Traversal in Python

from collections import deque # Algorithm to traverse all the nodes def Breadth_First_Traversal(Graph, Root_Node): visited = set() queue = deque([Root_Node]) visited.add(Root_Node) while queue: # Dequeue a vertex from queue vertex = queue.popleft() print(str(vertex) + " ", end="") for all_neighbour in Graph[vertex]: if all_neighbour not in visited: visited.add(all_neighbour) queue.append(all_neighbour) if __name__ == '__main__': Graph = {0: [1, 3], 1: [3], 2: [1], 3: [1, 2]} print("Breadth First Traversal: ") Breadth_First_Traversal(Graph, 0)