Consider the following graph.

Among the following sequences

I. a b e g h f

II. a b f e h g

III. a b f h g e

IV. a f g h b e Which are depth first traversals of the above graph?

1. AI, II, and IV only
2. BI and IV only
3. CII, III, and IV only
4. DI, III, and IV only

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: D. I, III, and IV only

Explanation

Edges: a–b, a–e, a–f, b–e, b–f, b–h, f–h, f–g, h–g, e–g. I (a b e g h f) and III (a b f h g e) and IV (a f g h b e) each move to an unvisited neighbour of the latest vertex. In II, after a b f the next vertex e is not adjacent to f while f still has unvisited neighbours, so II is not a DFS.