## Minimum Spanning Tree

**Algorithm:** Prim's MST
Input : G, a connected, weighted, undirected graph with n vertices and e edges
r, a vertex in G
Output: T a minimum weight spanning tree for G
0. mark each vertex's parent as "unknown" except r, which has parent nil ← i.e. only r is in the current MST
1. select vertex v with parent "unknown" with edge (u,v), where u's parent is
not "unknown", such that (u,v) has minimum weight amongst all such edges
2. set v's parent to u ← i.e. add v to thecurrent MST by connecting it to u
3. goto Step 1

## Proof that Prim's algorithm gives a minimum spanning tree

First we have to prove that the greedy algorithm is always part
of some optimum solution.

**Theorem:** If $T'$ is a subtree of a minimum spanning tree
for $G$, then there is a complete minimum spanning tree for
$G$, call it $T$, that contains $T'$ and contains the edge $(u,v)$
that is the minimum weight edge from a vertex in $T'$ to a
vertex not in $T'$.

**Proof:**
Let $T^*$ be a spanning tree that contains $T'$ but does not contain the
edge $(u,v)$. We will show how to "repair" it to create a
tree that still contains $T'$, but also contains $(u,v)$,
without increasing the total weight of the resulting tree.
The unique path from $u$ to $v$ in
$T^*$ leaves $T'$ along some edge $(y,z)$, i.e. $y$ is in
$T'$, but $z$ is not. If we delete $(y,z)$ we have two
disconnected trees, the one containing $u$ and the one
containing $v$. If we then add the edge $(u,v)$, we
reconnect the two trees, resulting in a new spanning
tree, call it $T$. Since the weight of $(u,v)$ $\le$ the
weight of $(y,z)$, the overall weight of $T$ is $\le$ the
overall weight of $T^*$.

Second, we have to prove that finding an optimum solution to
the smaller subproblem yields an optimum solution to the
original problem.
At first this is a bit confusing, because the way we've
phrased Prim's algorithm, it's not clear that we have a
"smaller problem of the same kind" to solve. So let's imagine
specifying the problem Prim's algorithm is solving in a
slightly different way:

Problem: Minimum Weighted Spanning Tree (containing proscribed subtree)
Given: a connected Graph G (V is the set of vertices, E the set of edges)
a subtree T' of G spanning the vertex set R, which is a subset of V
Find : a spanning tree T of the graph G that contains T' as a subtree
and has minimum weight over all such spanning trees.

Hopefully you see that Prim's algorithm can be viewed as
solving a sequence of such problems, where $|V-R|$ gets
smaller at each step. Now what we have to prove is trivial,
because a solution to the "smaller sub-problem"

*is* a
solution to the original problem, and therefore finding an
optimal solution to the smaller subproblem is indeed the right
thing to do.