Consider the following graph:

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:

Correct option is D

Depth-First Search (DFS) algorithm explores a graph by visiting all vertices starting from a specific vertex and exploring as far as possible along each branch before backtracking. In a graph with multiple connected components, DFS is performed on each component separately.
The order of traversal in DFS depends on the starting vertex and the sequence of edges being traversed. For the given graph, the DFS order can vary but must adhere to the rules of visiting a vertex completely before backtracking.
(A) abcghf: This is a valid DFS order. Starting from vertex a, it explores the path to b, then c, and further explores the path to g, h, and finally f.
(B) abfhc: This is not a valid DFS order. The sequence does not follow DFS rules since it skips the edge from g to f and directly jumps from b to f.
(C) abfhgc: This is a valid DFS order. Starting from a, it explores b, then f, followed by h, backtracks to explore g, and then moves to c.
(D) afgbhc: This is also a valid DFS order. Starting from a, it explores f, then g, backtracks to b, and finally visits h and c.
Correct Answer: (d) (A), (C), and (D) only
Information Booster:
1. DFS Characteristics:
· Uses a stack (either explicitly or via recursion).
· Effective for pathfinding and topological sorting.
2. Applications of DFS:
· Detecting cycles in a graph.
· Finding connected components in an undirected graph.
· Solving mazes and puzzles.
3. Key Difference Between BFS and DFS:
· BFS uses a queue and explores level by level.
· DFS dives deep into each branch before backtracking.
Additional Knowledge:
· (B) abfhc: Does not maintain DFS consistency as it does not visit all vertices in sequence before backtracking.
· DFS traversal order is not unique and can vary based on the adjacency list order or starting vertex.