Demo quiz — InfraDrill

Question 1 of 20 · 0 answered0:00

Two traversals share the same skeleton: take a vertex from a pending collection, mark it, add its unmarked neighbours to that collection, repeat. One uses a queue and the other a stack. On a graph where the goal is three edges from the start and a side branch is a thousand vertices deep, what does each do?

The stack version reaches the goal first, because it commits to one path rather than expanding every direction, and a goal only three edges away is found before the deep branch is entered at allThe queue version reaches the goal after examining everything within three edges; the stack version reaches it in the same number of steps, because both examine every vertex once and the goal's distance bounds the work either wayThe queue version reaches the goal after examining everything within three edges, because it finishes each distance before starting the next; the stack version may descend the deep branch first and examine far more before coming backBoth reach the goal in the same number of steps on any connected graph, since the collection's discipline changes the order of visits but not which vertices are visited before the goal is marked