= Solution
Sort <edges> by weight and then lexicographically. <Kruskal's algorithm> accepts \b[$(1,2),(4,6),(1,3),(2,4),(4,5)$], again of total weight \b[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>.
Back to article page
