M.Sc AI Practical Assignment Solution 4

Question:

Write a Python program to implement Breadth First Search Traversal.

Code:

from collections import deque

# Function to perform BFS traversal
def bfs(graph, start):
    visited = set()  # Set to keep track of visited nodes
    queue = deque([start])  # Queue for BFS traversal

    while queue:
        node = queue.popleft()  # Dequeue a node from the queue
        if node not in visited:
            print(node, end=" ")  # Process the node (e.g., print or perform some operation)
            visited.add(node)  # Mark the node as visited

            neighbors = graph[node]  # Get the neighbors of the current node
            for neighbor in neighbors:
                if neighbor not in visited:
                    queue.append(neighbor)  # Enqueue the neighbor for further exploration

# Example graph represented as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

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

Output:

BFS Traversal:
A B C D E F