Write a python program to implement Breadth First Search Traversal

Introduction

Breadth-First Search (BFS) is a fundamental graph traversal algorithm. It explores the vertices of a graph layer by layer, moving outward from the starting vertex. BFS is particularly useful in finding the shortest path in an unweighted graph and is widely used in various fields like networking, AI, and many more.

In this tutorial, we'll guide you through implementing BFS in Python.

Prerequisites

Before starting, ensure you have a basic understanding of:

• Python programming.
• Graphs and their representation (Adjacency List).

Step 1: Understanding the Graph Representation

A graph consists of nodes (vertices) connected by edges. There are different ways to represent a graph in programming:

1. Adjacency Matrix
2. Adjacency List (most common and efficient)

In this tutorial, we'll use an adjacency list to represent the graph.

Step 2: The BFS Algorithm

The BFS algorithm follows these steps:

• 1. Start at the source vertex.
• 2. Enqueue the source vertex.
• 3. While the queue is not empty:

• Dequeue a vertex from the queue.
• For each unvisited neighbor, mark it as visited and enqueue it.

Step 3: Implementing BFS in Python

Now, let's write a Python program to implement BFS:

from collections import deque
# Function to perform BFS traversal
def bfs(graph, start_vertex):
visited = set() # To keep track of visited vertices
queue = deque([start_vertex]) # Queue to hold vertices for BFS

while queue:
vertex = queue.popleft() # Dequeue a vertex from the queue

if vertex not in visited:
print(vertex, end=" ") # Print the vertex
visited.add(vertex) # Mark vertex as visited

# Enqueue all unvisited adjacent vertices
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)

# Example graph represented as an adjacency list

graph = {

    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F', 'G'],
    'D': [],
    'E': [],
    'F': [],
    'G': []
}

# Perform BFS starting from vertex 'A'
print("BFS traversal starting from vertex A:")
bfs(graph, 'A')

Step 4: Running the Program

Save the code in a `.py` file and run it. The expected output for the given graph is:

BFS traversal starting from vertex A:
A B C D E F G

Explanation of the Output

• The program starts from vertex 'A', enqueues it, and then visits its neighbors 'B' and 'C'.
• Next, it visits 'B', enqueues its neighbors 'D' and 'E'.
• Then, it visits 'C', enqueues its neighbors 'F' and 'G'.
• Finally, it visits each of the remaining vertices 'D', 'E', 'F', and 'G'.

This output shows that BFS visits vertices layer by layer.

Conclusion

You've successfully implemented the Breadth-First Search (BFS) traversal in Python! This basic understanding of BFS will be a valuable tool in your data structures and algorithms toolkit.

Feel free to modify the graph and experiment with different start vertices to see how the BFS traversal changes.

Practice Problem : Try implementing the BFS algorithm for a graph that includes cycles and observe how the visited set prevents reprocessing of vertices. 

Happy coding!