Graph Theory37 sections · 1633 units
Open in Course

Quiz: Kruskal vs Prim on Dense Graphs

Knowledge check

Check Your Understanding

For dense graphs where EV2E \approx V^2, which algorithm has better time complexity?

  1. A.Kruskal, because sorting edges is efficient
  2. B.Prim, because O(ElogV)O(E \log V) beats O(ElogE)O(E \log E) when EV2E \approx V^2
  3. C.Both have the same time complexity on dense graphs
  4. D.Kruskal, because Union-Find operations are nearly O(1)O(1)
Start the roadmap to answer the quizzes and solve the challenges