Python: BFS (Breadth-First Search) in Graphs

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

    def add_edge(self, u, v):
        # Add an edge to the adjacency list
        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=" ")
                visited.add(vertex)

                # 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()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)

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

Continue Learning with Java Guides

Want to take your programming skills to the next level? Explore my practical Udemy courses on Java, Spring Boot, Microservices, Full-Stack Development, Docker, and Generative AI. You can also follow my structured learning roadmaps to become a professional developer.

Explore My Udemy Courses View Developer Roadmaps

By Ramesh Fadatare - Udemy Instructor Partner