It is a <greedy algorithm> because it commits at every step to the cheapest remaining edge that can be added without creating a <graph cycle>, without revising earlier choices. The <minimum spanning tree cut property> explains why these locally cheapest admissible choices can be extended to an optimal spanning tree.

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 / c / Solution

 Solution (source code)