10.1 Finding Shortest Paths in Unweighted Graphs with Breadth-First Search

Breadth-first search (BFS) is the simplest shortest path algorithm. When every edge in a graph has the same cost, BFS discovers vertices in increasing order of distance from the starting vertex. The first time a vertex is reached, the algorithm has already found the shortest possible path to it.

This property makes BFS one of the most important graph algorithms. Many advanced shortest path techniques build upon ideas that first appear in BFS, including frontier expansion, distance labeling, path reconstruction, and state-space search.

In this recipe, you'll use BFS to compute shortest distances and reconstruct shortest paths in an unweighted graph.

Problem

Given an unweighted graph and a starting vertex, find the shortest distance from the source to every reachable vertex and reconstruct the shortest path to a target vertex.

Consider the following graph:

A -- B -- D
|    |
|    |
C -- E -- F

Starting from A, we want to determine the shortest path to every vertex.

Solution

Maintain three structures:

• A queue of vertices waiting to be explored
• A distance array storing shortest known distances
• A predecessor array storing the parent of each vertex

The BFS algorithm proceeds level by level.

package main

import "fmt"

func bfs(graph map[int][]int, source int) ([]int, []int) {
	n := len(graph)

	dist := make([]int, n)
	parent := make([]int, n)

	for i := range dist {
		dist[i] = -1
		parent[i] = -1
	}

	queue := []int{source}
	dist[source] = 0

	for len(queue) > 0 {
		v := queue[0]
		queue = queue[1:]

		for _, next := range graph[v] {
			if dist[next] != -1 {
				continue
			}

			dist[next] = dist[v] + 1
			parent[next] = v
			queue = append(queue, next)
		}
	}

	return dist, parent
}

func main() {
	graph := map[int][]int{
		0: {1, 2},
		1: {0, 3, 4},
		2: {0, 4},
		3: {1},
		4: {1, 2, 5},
		5: {4},
	}

	dist, parent := bfs(graph, 0)

	fmt.Println(dist)
	fmt.Println(parent)
}

Output:

[0 1 1 2 2 3]
[-1 0 0 1 1 4]

The distance array shows the minimum number of edges required to reach each vertex.

How It Works

BFS explores vertices in layers.

The source vertex forms layer 0.

Layer 0:
A

Its neighbors form layer 1.

Layer 1:
B C

Previously unseen neighbors of those vertices form layer 2.

Layer 2:
D E

Finally:

Layer 3:
F

The discovery order is therefore:

A
B C
D E
F

Every edge contributes exactly one unit of cost. Since BFS processes vertices in increasing layer order, no shorter path can exist once a vertex has been discovered.

The distance assignment follows:

Vertex	Distance
A	0
B	1
C	1
D	2
E	2
F	3

These values represent shortest path lengths measured in edges.

Reconstructing a Path

Distances alone are often insufficient. Most applications require the actual route.

The predecessor array stores the vertex from which each node was first reached.

Suppose the parent array contains:

A <- nil
B <- A
C <- A
D <- B
E <- B
F <- E

To reconstruct the path from A to F:

func buildPath(parent []int, target int) []int {
	var path []int

	for target != -1 {
		path = append(path, target)
		target = parent[target]
	}

	for i, j := 0, len(path)-1; i < j; i, j = i+1, j-1 {
		path[i], path[j] = path[j], path[i]
	}

	return path
}

The resulting path becomes:

A -> B -> E -> F

The reconstruction cost is proportional to the path length.

Discussion

The most important invariant in BFS is:

Every vertex removed from the queue already has its final shortest-path distance.

This invariant holds because vertices enter the queue in nondecreasing distance order.

Assume a vertex v has distance k.

Every vertex at distance less than k has already been processed.

Any undiscovered path to v would therefore contain at least k edges.

Consequently, the first discovered path must be optimal.

This argument forms the correctness proof for BFS shortest paths.

Complexity

Let:

• V be the number of vertices
• E be the number of edges

Each vertex enters the queue once.

Each edge is examined once in a directed graph and twice in an undirected graph.

Therefore:

Operation	Complexity
BFS traversal	O(V + E)
Distance lookup	O(1)
Path reconstruction	O(path length)
Memory usage	O(V)

This linear complexity is one reason BFS appears so frequently in practical systems.

Variations

Several important algorithms are direct extensions of BFS:

• Multi-source BFS
• Bidirectional BFS
• 0-1 BFS
• BFS on grids
• BFS on implicit state spaces
• Shortest transformation sequence problems
• Connected-component discovery

Many interview problems that appear unrelated to graphs can be modeled as BFS over a state graph whose vertices are states and whose edges represent valid transitions.

Common Pitfalls

Failing to mark vertices when they are enqueued often causes duplicates in the queue.

Using a stack instead of a queue converts the algorithm into depth-first search and destroys shortest-path guarantees.

Attempting to use BFS on weighted graphs generally produces incorrect answers because BFS assumes every edge contributes identical cost.

Forgetting to store predecessors makes path reconstruction impossible without running another search.

Takeaway

Breadth-first search is the canonical shortest path algorithm for unweighted graphs. Its central idea is simple: explore vertices in increasing distance order using a queue. This guarantees that the first path discovered to any vertex is optimal. Once you understand BFS and its distance-layer invariant, the transition to weighted shortest path algorithms such as Dijkstra becomes much more natural.