# Important Variants

Understand the variants' applications in problem solving.

## We'll cover the following

## 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.

Create a free account to access the full course.

By signing up, you agree to Educative's Terms of Service and Privacy Policy