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.