Important Variants

Stack: depth-first

If we implement the “bag” using a stack, we recover our original depth-first search algorithm. Stacks support insertions (push) and deletions (pop) in $O(1)$ time each, so the algorithm runs in $O(V + E)$ time. The spanning tree formed by the parent edges is called a depth-first spanning tree. The exact shape of the tree depends on the start vertex and on the order that neighbors are visited inside the loop $(†)$, but in general, depth-first spanning trees are long and skinny. We will consider several important properties and applications of depth-first search later.

Queue: breadth-first

If we implement the “bag” using a queue, we get a different graph-traversal algorithm called breadth-first search. Queues support insertions (push) and deletions (pull) in $O(1)$ time each, so the algorithm runs in $O(V + E)$ time. In this case, the breadth-first spanning tree formed by the parent edges contains the shortest paths from the start vertex $s$ to every other vertex in its component; we’ll consider the shortest paths in detail later. Again, the exact shape of a breadth-first spanning tree depends on the start vertex and on the order that neighbors are visited in the for loop $(†)$, but in general, breadth-first spanning trees are short and bushy.

Priority queue: best-first

Finally, if we implement the “bag” using a priority queue, we get yet another family of algorithms called best-first search. Because the priority queue stores at most one copy of each edge, inserting an edge or extracting the minimum-priority edge requires $O(\log E)$ time, which implies that best-first search runs in $O(V + E\log E)$ time.

We describe best-first search as a “family of algorithms,” rather than a single algorithm, because there are different methods to assign priorities to the edges, and these choices lead to different algorithmic behavior. We’ll describe three well-known variants below, but there are many others. In all three examples, we assume that every edge $uv$ or $u\rightarrow v$ in the input graph has a non-negative weight $w(uv)$ or $w(u\rightarrow v)$.

First, if the input graph is undirected and we use the weight of each edge as its priority, best-first search constructs the minimum spanning tree of the component of $s$. Surprisingly, as long as all the edge weights are distinct, the resulting tree doesn’t depend on the start vertex or the order that neighbors are visited; in this case, the minimum spanning tree is actually unique. This instantiation of best-first search is commonly (but, as usual, incorrectly) known as Prim’s algorithm; we’ll discuss this and other minimum spanning trees in more detail later.

The algorithm runs as follows. We define the length of a path to be the sum of the weights of its edges. We can also compute shortest paths in weighted graphs using best-first search, as follows. Every marked vertex $v$ stores a distance $dist(v)$. Initially, we set $dist(s) = 0$. For every other vertex $v$, when we set $parent(v) ← p$, we also set $dist(v) ← dist(p) + w(p\rightarrow v)$, and when we insert the edge $v\rightarrow w$ into the priority queue, we use the priority ...