# Breadth-First Search — Data Structures & Algorithms

Source: https://www.geekswithgeeks.com/en/dsa/bfs

> Explore a graph level by level with a queue — finds shortest paths in unweighted graphs.

## Rings around the start

BFS visits all nodes 1 edge away, then all 2 edges away, and so on. A **queue** enforces this order and a **visited set** prevents revisiting. The first time you reach a node is via a shortest path (in edges). `O(V + E)`.

## Shortest path length

Track distance as you enqueue each neighbour for the first time.

```python
from collections import deque
def shortest(g, start, goal):
    q = deque([(start, 0)])
    seen = {start}
    while q:
        node, d = q.popleft()
        if node == goal:
            return d
        for nb in g[node]:
            if nb not in seen:
                seen.add(nb)
                q.append((nb, d + 1))
    return -1
```

## Where it fits

Shortest path in a maze/grid, "minimum steps to...", level-order tree traversal, word ladders, and flood fill. If edges have weights, upgrade to Dijkstra.