Graph Theory37 sections · 1633 units
Open in Course

Quiz: 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?

  1. A.Because DFS does not work on directed graphs
  2. B.Because the original graph might have self-loops
  3. C.Because directed reachability is not symmetric. Reaching vv from uu does not mean vv can reach uu
  4. D.Because a single DFS always visits all nodes
Start the roadmap to answer the quizzes and solve the challenges