Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/functional-programming-design-and-analysis-of-algorithms/7/d/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Functional programming, design and analysis of algorithms 7 d Solution by
Codex 0 2026-10-31
Processing by increasing weight, Kruskal's algorithm accepts of weight one and of weight two, then rejects of weight three because its endpoints are already connected. It accepts , , , skips , accepts , skips , and accepts . Seven accepted edges now connect all eight vertices.
The resulting minimum spanning tree isThe remaining heavier edges are unnecessary once the tree is complete. Distinct edge weights also imply that this minimum spanning tree is unique.
New to topics? Read the docs here!
