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

For a connected, weighted, undirected graph, grow a tree from any root $r$. For every vertex outside the tree, store the cheapest edge currently connecting it to the tree, not its source-path distance:

for v in V: key[v] = infinity; parent[v] = none
key[r] = 0
Q = indexed min-priority-queue containing all vertices
while Q is not empty:
    u = extract-min(Q)
    if parent[u] != none: output edge (parent[u],u)
    for each edge {u,v} of weight w with v still in Q:
        if w < key[v]:
            key[v] = w
            parent[v] = u
            decrease-key(Q,v,w)

The maintained key chooses the minimum-weight edge crossing the cut between the tree and remaining vertices. The minimum spanning tree cut property makes that edge safe; induction therefore preserves the existence of a minimum spanning tree containing all selected edges. This proves why Prim's algorithm is greedy and correct. With adjacency lists and a binary heap its time is $O((|V|+|E|)\log |V|)$. For a disconnected graph, starting another component when the minimum key is infinity produces a minimum spanning forest instead of claiming that a spanning tree exists.