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?

In DFS, we keep moving to an unvisited adjacent vertex as deeply as possible.

Check I:

$a\to b\to e\to g\to h\to f$

All consecutive vertices are connected, so I is possible DFS traversal.

Check II:

$a\to b\to f\to e$

Here, $f$ is not directly connected to $e$.

Also, from $f$, unvisited adjacent vertices like $h$ and $g$ are available, so DFS cannot jump to $e$.

So, II is not possible.

Check III:

$a\to b\to f\to h\to g\to e$

All consecutive vertices are connected, so III is possible DFS traversal.

Check IV:

$a\to f\to g\to h\to b\to e$

All consecutive vertices are connected, so IV is possible DFS traversal.

Therefore, valid DFS traversals are I, III, and IV only.