Graph Theory37 sections · 1633 units
Open in Course

Quiz: DFS on Trees

Knowledge check

Check Your Understanding

You run DFS on a rooted tree and pass a parent parameter to avoid revisiting the parent. Why is this enough to prevent cycles in a tree, but not in a general graph?

  1. A.Trees have directed edges, so you can only go one way
  2. B.Trees have fewer edges, so collisions are rare
  3. C.The parent parameter acts as a full visited array
  4. D.Trees have exactly 11 path between any 22 nodes, so blocking the parent blocks the only back-edge
Start the roadmap to answer the quizzes and solve the challenges