Depth-first visiting order — Aptitude Question
Depth-first visiting order: An undirected graph has these adjacency lists: | Vertex | Adjacent vertices |… Answer and worked solution on CodeKairo.
- Topic: Data Structures & Algorithms
- Section: Programming MCQs
- Difficulty: Medium
- Time target: 120 seconds
Question
An undirected graph has these adjacency lists:
| Vertex | Adjacent vertices |
|---|---|
| A | B, C |
| B | A, D |
| C | A, E |
| D | B, E |
| E | C, D, F |
| F | E |
A depth-first search starts at A and always moves to the unvisited neighbour that comes first alphabetically. In what order are the vertices visited?
Options
- A, B, C, D, E, F
- A, B, D, E, C, F
- A, B, D, E, F, C
- A, C, E, D, B, F
Show the answer and the worked solution
Correct answer: B. A, B, D, E, C, F
Worked solution
- From A the alphabetically first neighbour is B, so B is visited.
- B's neighbours are A (visited) and D, so D is visited.
- D's neighbours are B (visited) and E, so E is visited.
- E's unvisited neighbours are C and F, and C comes first; C is visited, and both of C's neighbours are already visited.
- Backtracking to E leaves F, which is visited last, giving A, B, D, E, C, F.
Answer: A, B, D, E, C, F.
The idea
A DFS order is fixed only once the tie-breaking rule is fixed. Backtracking is the step candidates forget: the walk resumes at the deepest vertex that still has an unvisited neighbour.
Shortcut. A → B → D → E is forced; at E the alphabetical rule picks C before F, and C is a dead end, so F comes last.
Common trap. "A, B, C, D, E, F" is the breadth-first order, visiting A's neighbours B and C before going deeper.
All Data Structures & Algorithms questions · placement mock tests