What is breadth-first search (BFS)?

Question

IT Interview Practice · Accepted Answer

**BFS** explores a graph level by level, visiting all neighbors of a node before moving deeper. It uses a **queue** and finds the **shortest path** (fewest edges) in unweighted graphs.

## The idea

Start at a source, enqueue it, then repeatedly dequeue a node, visit its unvisited neighbors, and enqueue them. A `visited` set prevents revisiting.

## Example

```python
from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()        # FIFO: explore nearest first
        order.append(node)
        for nbr in graph[node]:
            if nbr not in visited:
                visited.add(nbr)
                queue.append(nbr)
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
bfs(graph, 'A')                        # -> ['A', 'B', 'C', 'D']
```

## Complexity

- **Time:** O(V + E) — each vertex and edge once.
- **Space:** O(V) for the queue and visited set.

## When to use / pitfalls

Use BFS for **shortest path in unweighted graphs**, level-order traversal, and finding connected components. It uses more memory than DFS (a whole frontier at once). Always track `visited` or you may loop forever on cycles.

## Why it matters

BFS is *the* algorithm for shortest paths when every edge counts equally — routing, web crawling, social-network degrees of separation.

Its queue-based, level-by-level structure is a fundamental traversal pattern.

Knowing BFS vs DFS lets you pick the right tool for reachability, paths, and ordering problems.

The idea

Example

Complexity

When to use / pitfalls

Why it matters

Related questions