Which of the following is application of depth-first search?
2019
Which of the following is application of depth-first search?
- A.
Only topological sort
- B.
Only strongly connected components
- C.
Both topological sort and strongly connected components
- D.
Neither topological sort nor strongly connected components
Attempted by 208 students.
Show answer & explanation
Correct answer: C
Answer: Both topological sort and strongly connected components
Why: Depth-first search (DFS) explores reachable vertices and records finishing times. These properties are the basis for several graph algorithms, including the two listed applications.
Topological sort: On a directed acyclic graph, run DFS and output vertices in reverse order of their finishing times (decreasing finish time). This produces a valid topological ordering. Time complexity: O(V + E).
Strongly connected components: Algorithms that find SCCs use DFS. Kosaraju's algorithm runs DFS to get finish times, then runs DFS on the transposed graph in decreasing finish order to collect components. Tarjan's algorithm uses a single DFS with a stack and low-link values to produce SCCs. Both run in O(V + E).
Because DFS directly supports both of these procedures, the correct answer is that DFS applies to both topological sort and strongly connected components.
A video solution is available for this question — log in and enroll to watch it.