Prims algorithm

Overarching idea

Build a subgraph by repeatedly choosing the minimum edge connecting the subgraph to another vertice.

Steps

  1. Choose a vertex as the initial MST subgraph, S.

  2. Choose the minimum edge which connects S to any other vertex in the graph, G. This vertex should not be connected to S.

  3. Repeat step 2.

Proof of correctness

Proof by contradiction

Assume Prim’s algorithm does not given an MST.

Let M be a MST for a weighted graph G = (V, E).

We know PRIM constructs a sequence of trees \(T_{i}\), where \(T_{i}\) contains i vertices and i-1 edges.

Let \(T_{k+1}\) be the first tree that has an edge not contained in the MST.

Using the cut property to \(T_{k}\) and \(V - T_{k}\):

  • The min cost edge from \(T_{k}\) to \(V - T_{k}\) must be in min spanning tree

  • Prim’s algorithm chooses that edge by definition

  • Hence \(T_{k+1}\) must have the same edges as the MST.

logo