BFS

BFS, or breadth-first search, visits vertices in layers from a starting point. It processes all vertices at distance one before vertices at distance two.

BFS uses a queue to preserve discovery order.

Core Idea

The algorithm starts with one vertex, records it as visited, and places it in a queue. It repeatedly removes the oldest queued vertex and adds its unvisited neighbors.

Because of this layer order, BFS finds shortest paths in an unweighted graph.

The queue is what creates the layer order. Newly discovered neighbors wait behind all earlier discovered vertices. That prevents a path of length three from being processed before all paths of length two have had a chance.

Function Contracts

bfs(graph, start) expects an adjacency list and a start vertex that appears as a key in graph. It prints vertices in breadth-first order.

distances(graph, start) uses the same graph shape and returns a dictionary. distance[node] is the minimum number of edges from start to node in an unweighted graph.

Python Example

from collections import deque
 
def bfs(graph, start):
    visited = {start}
    queue = deque([start])
 
    while queue:
        node = queue.popleft()
        print(node)
 
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

The visited set prevents repeated processing.

Distance Version

BFS often stores distance from the start:

from collections import deque
 
def distances(graph, start):
    distance = {start: 0}
    queue = deque([start])
 
    while queue:
        node = queue.popleft()
 
        for neighbor in graph[node]:
            if neighbor not in distance:
                distance[neighbor] = distance[node] + 1
                queue.append(neighbor)
 
    return distance

The first time a vertex is discovered, its distance is final for an unweighted graph.

Step-by-Step Shape

If A connects to B and C, and B connects to D, BFS from A processes:

A
B, C
D

Those are distance layers: distance 0, then distance 1, then distance 2.

Complexity

With an adjacency list, BFS is O(V + E) because each vertex is enqueued at most once and each edge is inspected a limited number of times.

The queue and visited set use O(V) space.

Common Confusions

BFS shortest path means shortest by number of edges. It does not handle different edge weights by itself.

Marking a node visited when it is enqueued avoids adding the same node many times.

Do not wait until dequeue time to mark visited unless you intentionally handle duplicates. Marking when enqueued is the simpler default.

When To Use It

Use BFS for level-order traversal, shortest paths in unweighted graphs, minimum moves where every move has equal cost, and finding all nodes reachable from a start.

Use a different shortest-path algorithm when edge costs differ.

The Main Point

BFS uses a queue to process vertices by distance layers. That queue discipline is what makes unweighted shortest paths work.