Graph Theory37 sections · 1633 units
Open in CourseQuiz: Kosaraju's First DFS
Knowledge check
Check Your Understanding
In Kosaraju's algorithm, the first DFS records finish order. Why can't you just run a single DFS on the original graph and group nodes by their connected components?
- A.Because DFS does not work on directed graphs
- B.Because the original graph might have self-loops
- C.Because directed reachability is not symmetric. Reaching from does not mean can reach
- D.Because a single DFS always visits all nodes