In an undirected graph, the neighbors of each vertex are A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. A recursive depth-first search starts from vertex A. The neighbors are examined in the order listed, and as soon as an unvisited vertex is found, the search moves to it. In what order are the vertices visited?

Answer: C. A, B, D, E, F, C

From A the search moves to B, then to D, the first unvisited neighbor of B. D's only neighbor, B, is already visited, so it returns to B and moves on to E, then from E to the unvisited F, and from F to its neighbor C. The order is therefore A, B, D, E, F, C. A, B, C, D, E, F is the breadth-first search order, which visits vertices nearest-first. A, B, D, E, C, F turns back from E without going to the unvisited F, so it is not a depth-first order.

• A. This is the breadth-first search order, which visits vertices nearest-first.
• B. E has an unvisited neighbor F, so the search goes to F before returning toward C.
• C. Correct. The search goes as far as it can and backtracks only at dead ends.