# Prim's algorithm

1,016pages on
this wiki

Prim's algorithm is a common method for finding a minimal spanning tree of a connected, weighted, undirected graph. It is a greedy algorithm and, surprisingly, is always correct despite its simplicity. It is not hard at all to execute this algorithm with pencil and paper. However, its proof is a little more involved.

## Algorithm

Let $G = (V,E)$ be a connected undirected graph, let $w(e)$ be a bijection from its edges to their weights and let $T = (V_n,E_n)$ be a graph that will form a minimal spanning tree of $G$, where $V_n$ and $E_n$ are initially empty.

### Initial Stage

1. Select an edge $e \in E$ such that $e$ minimizes $w(e)$. If there is more than one choice, pick out any one arbitrarily. Add $e$ to $E_n$ and add its endpoints to $V_n$.

### Iterative Stage

1. Select an edge $e \in E - E_n$ adjacent to $T$ such that $e$ minimizes $w(e)$. As before, if there is more than one edge that minimizes weight, the choice is arbitrary. Add $e$ to $E_n$ and add the endpoint of $e$ that is not currently in $V_n$ to $V_n$.
2. Repeat previous step until $|E_n| = |V| - 1$, i.e. until the minimal spanning tree has one less edge than the number of vertices. This step indicates the algorithm is complete, since a tree with $n$ vertices necessarily has $n-1$ edges.