# 1. Introduction

The Breadth-First Search (BFS) is another fundamental algorithm used to explore nodes and edges of a graph. It visits nodes level by level. Starting from a source node, BFS explores all of its neighbors at the present depth before moving on to nodes at the next depth level.

# 2. Program Overview

In this program, we will:

1. Create a representation for a graph using an adjacency list.

2. Implement the BFS algorithm to traverse through the graph and print each vertex.

# 3. Code Program

class Graph:
def __init__(self):
# Dictionary to store the adjacency list of the graph
self.graph = dict()

if u not in self.graph:
self.graph[u] = []
self.graph[u].append(v)

def bfs(self, start_vertex):
# Mark the source node as visited and enqueue it
visited = set()
queue = [start_vertex]

while queue:
# Dequeue a vertex from the queue and print it
vertex = queue.pop(0)
if vertex not in visited:
print(vertex, end=" ")

# Enqueue all adjacent vertices of the dequeued vertex
for neighbour in self.graph[vertex]:
if neighbour not in visited:
queue.append(neighbour)

# Create a sample graph and add edges
g = Graph()

# Perform BFS from vertex 2
print("BFS starting from vertex 2:")
g.bfs(2)

### Output:

BFS starting from vertex 2:
2 0 3 1

# 4. Step By Step Explanation

1. The Graph class initializes an empty graph using a dictionary to represent the adjacency list.

2. The add_edge method allows us to add edges to the graph.

3. The bfs method performs a breadth-first traversal of the graph. It uses a set visited to track the visited vertices and a queue to maintain the BFS traversal order.

4. In the sample provided, we created a graph with 4 vertices and executed BFS starting from vertex 2. The output displays the order in which nodes are visited following BFS.