What is BFS

Breadth-first search (BFS) is a graph traversal algorithm that explores nodes level by level. Starting from a source node, it visits all immediate neighbors first, then all neighbors of those neighbors, then the next layer, and so on. It uses a queue to maintain this order and finds the shortest path in unweighted graphs.

How it works

BFS follows a simple loop:

1. Enqueue the starting node and mark it as visited.
2. Dequeue a node from the front of the queue.
3. Process it — check if it is the target, record its distance, etc.
4. Enqueue all of its unvisited neighbors and mark them as visited.
5. Repeat until the queue is empty.

Graph:   A — B — E
         |   |
         C — D — F

BFS from A:
  Layer 0: [A]
  Layer 1: [B, C]        ← neighbors of A
  Layer 2: [E, D]        ← neighbors of B, C (not yet visited)
  Layer 3: [F]           ← neighbor of D (not yet visited)

Visit order: A, B, C, E, D, F

Because BFS explores in layers, the first time it reaches a node is always via the shortest path (fewest edges). This is why BFS is the standard algorithm for finding shortest paths in unweighted graphs.

The time complexity is O(V + E) where V is the number of vertices and E is the number of edges. Every node is enqueued and dequeued once, and every edge is examined once. Space complexity is O(V) for the queue and the visited set.

BFS can also determine if a graph is connected (can you reach every node from a starting node?), find all nodes within a certain distance, and detect if a graph is bipartite (two-colorable).

For weighted graphs where edges have different costs, BFS alone does not find the shortest path — you need Dijkstra's algorithm, which uses a priority queue instead of a regular queue. But for unweighted graphs and level-order problems, BFS is the right tool.

Why it matters

BFS is the foundation for shortest-path problems, network analysis, and any scenario where you need to explore outward from a starting point. Social network friend suggestions ("people 2 connections away"), web crawlers, and puzzle solvers (shortest moves to solve a Rubik's cube state) all use BFS. Its level-by-level guarantee makes it predictable and correct for distance-based queries.

See How Graph Algorithms Work for the full treatment of BFS, DFS, and shortest-path algorithms.