Past exam of the year 1 of the computer science course of the University of Oxford / 2022 / Functional programming, design and analysis of algorithms (resit) / 8 / b / Solution

Sort edges by weight and then lexicographically. Kruskal's algorithm accepts $(1,2),(4,6),(1,3),(2,4),(4,5)$, again of total weight 9.

The two weight-one edges $(1,2),(4,6)$ join different components. Among weight-two edges, $(1,3)$ is accepted, then $(2,4)$ joins the two larger components; $(3,4)$ would now create a cycle and is rejected. Among weight-three edges, $(1,4)$ is rejected for the same reason, and $(4,5)$ joins the remaining vertex. Five accepted edges connect all six vertices, so the algorithm can stop. The disjoint-set data structure implements precisely these component tests. The eponym is Joseph Kruskal.