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 ${\displaystyle G = (V, E)}$ be a connected undirected graph, let ${\displaystyle w(e)}$ be a bijection from its edges to their weights and let ${\displaystyle T = (V_n,E_n)}$ be a graph that will form a minimal spanning tree of ${\displaystyle G}$, where ${\displaystyle V_n}$ and ${\displaystyle E_{n}}$ are initially empty.

Initial Stage

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

Iterative Stage

1. Select an edge ${\displaystyle e \in E - E_n}$ adjacent to ${\displaystyle T}$ such that ${\displaystyle e}$ minimizes ${\displaystyle w(e)}$. As before, if there is more than one edge that minimizes weight, the choice is arbitrary. Add ${\displaystyle e}$ to ${\displaystyle E_{n}}$ and add the endpoint of ${\displaystyle e}$ that is not currently in ${\displaystyle V_n}$ to ${\displaystyle V_n}$.
2. Repeat previous step until ${\displaystyle |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 ${\displaystyle n}$ vertices necessarily has ${\displaystyle n-1}$ edges.

See also

• Proof of Prim's algorithm
• Kruskal's algorithm