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: DFS Applications. 
- **Topological Sort**: DFS is used to generate a topological ordering of vertices in a Directed Acyclic Graph (DAG). 

- **Determining Strongly Connected Components (SCCs)**: DFS can be used in algorithms like Kosaraju's algorithm to identify strongly connected components in a graph. 

- **Solving Maze Problem**: DFS is often applied to explore a maze by visiting each possible path and backtracking when necessary. 
 

Step 2: Incorrect Application. 
- **Finding minimum distance to a node in an unweighted graph optimally**: This task is usually solved using **Breadth-First Search (BFS)**, not DFS. BFS explores the graph level by level, ensuring the shortest path in an unweighted graph. 
 

Step 3: Conclusion. 
The correct answer is **(3) Finding minimum distance to a node in an unweighted graph optimally**.