Prim's Algorithm

Algorithm

The purpose of this algorithm is to produce a minimum spanning tree for any given weighted graph $G$.

Step 1: Choose any vertex of $G$, and add it to $T$.

Step 2: Add an edge of minimum weight $e$ to join a vertex in $T$ to one not in $T$.

Step 3: If $T$ spans $G$, stop. Otherwise, go to Step 2.

The above constitutes an algorithm, for the following reasons:

Finiteness

For each iteration through the algorithm, step 2 is executed, which increases the number of edges in $T$ by 1.

As a tree with $n$ nodes has $n-1$ edges, the algorithm will terminate after $n-1$ iterations.

Definiteness

Step 1: Trivially definite.

Step 2: As the edges connecting $T$ to the remaining vertices can be arranged in order of weight, there is a definite edge (or set of edges) with minimal weight.

Step 3: It is straightforward to determine whether all the vertices are connected.

Inputs

The input to this algorithm is the weighted graph $G$.

Outputs

The output to this algorithm is the minimum spanning tree $T$.

Effective

Each step of the algorithm is basic enough to be done exactly and in a finite length of time.

Note

It is clear that this is a greedy algorithm: at each stage the minimum possible weight is chosen, without any analysis as to whether there may be a combination of larger weights which may produce a smaller-weight spaning tree.

For this reason, it is sometimes called Prim's greedy algorithm.

In this case, the greedy algorithm does produce the minimum spanning tree.

Historical Note

This algorithm was initially developed in 1930 by Czech mathematician Vojtěch Jarník.

Robert Prim independently discovered it in 1957, and in 1959 it was rediscovered by Edsger Dijkstra.

For these reasons it is also known as the DJP Algorithm, the Jarník Algorithm, or the Prim-Jarník Algorithm.

Source of Name

This entry was named for Robert C. Prim.