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 $(†$, as explained in the algorithm in the previous lesson$)$, 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 will 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.