Can you show me a BFS code example in Python?

Can you show me a BFS code example in Python?

Sure! Here's a simple implementation of Breadth-First Search (BFS) in Python:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])

    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            queue.extend(neighbor for neighbor in graph[vertex] if neighbor not in visited)

    return visited

# Example usage:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(bfs(graph, 'A'))  # Output: {'A', 'B', 'C', 'D', 'E', 'F'}

What does this code do?

This code performs a BFS traversal on a graph starting from a specified node. It visits all reachable nodes.

Can you explain how the queue works in this example?

Certainly! The queue is used to keep track of the nodes that need to be explored. Nodes are added to the queue when they are discovered, and they are processed in the order they were added, ensuring that we explore all neighbors at the current depth before moving deeper.

What if I want to find the shortest path using BFS?

To find the shortest path, you can modify the BFS to keep track of the path taken to reach each node. You can use a dictionary to store the parent of each node and reconstruct the path once you reach the target.