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 / a

Start Prim's algorithm at vertex $1$, since the source does not specify a starting vertex. Write every undirected edge with its smaller endpoint first. With lexicographic tie-breaking, the accepted edges are $(1,2),(1,3),(2,4),(4,6),(4,5)$, of total weight 9.

Initially $(1,2)$ is the cheapest crossing edge. The next minimum is a weight-two tie between $(1,3)$ and $(2,4)$, so choose $(1,3)$. Then the weight-two tie between $(2,4)$ and $(3,4)$ is resolved in favour of $(2,4)$. Adding vertex $4$ exposes the weight-one edge $(4,6)$, which is selected next. Finally $(4,5)$ precedes $(5,6)$ among the weight-three choices. Every accepted edge crosses from the existing tree to a new vertex, as required by the minimum spanning tree cut property. A different starting vertex can produce a different accepted-edge order; the displayed answer fixes that unspecified choice. The algorithm is named for Robert C. Prim.