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?

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.