Shortest Paths in an Unweighted Graph From Breadth-First Search

In a graph whose edges all cost the same, the shortest path is the one with the fewest edges, and breadth-first search finds it to every vertex in one pass. This card adds two arrays to the search, a distance and a parent for each vertex, rebuilds paths from the parents, and shows why depth-first search cannot be used in its place.

When a vertex is first found, its distance is one more than the distance of the vertex that found it, and that vertex is its parent. The start has distance 0 and no parent. To rebuild the path to any vertex, follow parents back to the start and reverse the list. The table gives both searches' paths from A on the topic's graph, from a run; the depth-first column follows the tree of edges depth-first search used to first reach each vertex.

Breadth-first search's paths are shortest because of the order it works in. Every vertex at distance d joins the queue before any vertex at distance d + 1, since the vertices at d + 1 are found only while the vertices at d are being taken. So when a vertex is first found, every shorter route to it has already been tried, and the first parent it gets is on a shortest path. F, for one, gets D as its parent while D is taken, before E is, so F's path is A B D F.

Depth-first search makes no such promise. It reaches a vertex by whatever path it happened to follow, and on this graph it reaches C through B and D, 3 edges, although C is A's neighbour. Sorting the neighbours differently changes which paths it finds, never the fact that it can find a long one first.

The promise holds only when every edge costs the same. With weights, the path with the fewest edges can be the more expensive one, and Shortest Paths, later in Graph Algorithms, handles that case.