What is BFS Using Queue: Explanation and Example

Breadth-First Search (BFS) is a graph traversal method that explores nodes level by level using a queue to keep track of nodes to visit next. The queue ensures nodes are processed in the order they are discovered, starting from a chosen starting point.

How It Works

BFS starts at a chosen node and explores all its neighbors before moving to the neighbors' neighbors. Imagine you are at a party and want to greet everyone by moving outward from the person you know first, then their friends, and so on.

The queue helps by holding nodes waiting to be visited in the order they were found. When you visit a node, you add all its unvisited neighbors to the queue. This way, nodes closer to the start are visited before nodes farther away.

Example

This example shows BFS on a simple graph using a queue. It prints nodes in the order they are visited.

python

from collections import deque

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

    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            order.append(node)
            for neighbor in graph.get(node, []):
                if neighbor not in visited and neighbor not in queue:
                    queue.append(neighbor)
    return order

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

print(bfs(graph, 'A'))

Output

['A', 'B', 'C', 'D', 'E', 'F']

When to Use

BFS is useful when you want to find the shortest path or explore nodes in layers. For example, it helps in finding the shortest route in maps, social network connections, or solving puzzles where you move step-by-step.

It is also used in web crawlers to visit pages level by level and in networking to broadcast messages efficiently.

Key Points

• BFS uses a queue to explore nodes in order of discovery.
• It visits all neighbors of a node before moving deeper.
• It is ideal for finding shortest paths in unweighted graphs.
• It requires tracking visited nodes to avoid repeats.

Key Takeaways

BFS uses a queue to explore nodes level by level in a graph.

It visits all neighbors before moving to the next level.

BFS is great for shortest path problems in unweighted graphs.

A queue ensures nodes are processed in the order they are found.

Tracking visited nodes prevents infinite loops.