An undirected graph has edges A–B, A–C, B–D, B–E, C–F and E–F, and each adjacency list is kept in alphabetical order. What is the depth-first search order starting from A?
Correct answer D. A, B, D, E, F, C
Explanation
From A, DFS goes to its first neighbour B, then B's first unvisited neighbour D. D is a dead end, so it backtracks to B and visits E, then E's neighbour F, then F's unvisited neighbour C. That gives A, B, D, E, F, C. The order A, B, C, D, E, F is what breadth-first search produces, visiting level by level.
Answer checked How we write and check questions
Discussion