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

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.

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 is **0 1 3 2**.

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

- 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

- 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

- 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

- 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**:

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

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)
```

```
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)
```