Question

Which of the following is not an application of DFS?

• A. Topological Sort
• B. Determining Strongly Connected Components in a graph
• C. Finding minimum distance to a node in an unweighted graph optimally
• D. Solving Maze Problem

Hint:

Use BFS for finding the shortest path in unweighted graphs, as it explores all nodes at the present depth level before moving on to the next level.

Answer 1

The Correct Option is C

Step 1: Applications of Depth-First Search (DFS). 
- Topological Sorting: DFS is employed to establish a topological order of vertices within a Directed Acyclic Graph (DAG). 

- Identification of Strongly Connected Components (SCCs): DFS facilitates algorithms such as Kosaraju's algorithm for pinpointing strongly connected components in a graph. 

- Maze Solving: DFS is frequently utilized to navigate mazes by traversing all potential routes and retracing steps when required. 
 

Step 2: Misapplication. 
- Optimal determination of the shortest path to a node in an unweighted graph: This objective is typically achieved through Breadth-First Search (BFS), not DFS. BFS systematically explores the graph layer by layer, guaranteeing the shortest path in unweighted graphs. 
 

Step 3: Final Verdict. 
The accurate selection is (3) Finding minimum distance to a node in an unweighted graph optimally.