Breadth First Traversal for a Graph

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 is 0 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)