For the graph; the following sequences of depth first search $(DFS)$ are given

(A) $abcghf$
(B) $abfchg$
(C) $abfhgc$
(D) $afghbc$
Which of the following is correct?
🎥 Video solution / Text Solution of this question is given below:
Solution:
In DFS, we start from a vertex and keep going deeper through an unvisited adjacent vertex.
From the graph, important edges are:
$a-b,\ a-c,\ a-f,\ b-c,\ b-f,\ b-h,\ c-g,\ g-h,\ f-h,\ f-g$
Now check each DFS sequence.
Check (A): $abcghf$
Path followed:
$a\to b\to c\to g\to h\to f$
All these are valid edges:
$a-b,\ b-c,\ c-g,\ g-h,\ h-f$
So, sequence (A) can be a valid DFS order.
Check (B): $abfchg$
Path starts as:
$a\to b\to f$
After reaching $f$, there are still unvisited adjacent vertices such as $h$ and $g$.
DFS should go deeper from $f$ to one of its unvisited adjacent vertices.
But the next vertex in the sequence is $c$, and $f-c$ is not an edge.
So, sequence (B) cannot be a valid DFS order.
Check (C): $abfhgc$
Path followed:
$a\to b\to f\to h\to g\to c$
All these are valid edges:
$a-b,\ b-f,\ f-h,\ h-g,\ g-c$
So, sequence (C) can be a valid DFS order.
Check (D): $afghbc$
Path followed:
$a\to f\to g\to h\to b\to c$
All these are valid edges:
$a-f,\ f-g,\ g-h,\ h-b,\ b-c$
So, sequence (D) can be a valid DFS order.
Therefore, valid DFS sequences are:
(A), (C) and (D) only.