Prim's Algorithm

Algorithm

The purpose of this algorithm is to produce a minimum spanning tree $T$ 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$ is a spanning tree $G$, stop. Otherwise, go to Step 2.

Proof

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 minimum 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 from 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.

Also known as

It is clear that Prim's Algorithm 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 spanning tree.

For this reason, it is sometimes called Prim's Greedy Algorithm.

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

Also see

• Prim's Algorithm produces Minimum Spanning Tree
• Kruskal's Algorithm

Source of Name

This entry was named for Robert Clay Prim.

Historical Note

Prim's Algorithm was initially developed in $1930$ by Czech mathematician Vojtěch Jarník.

Robert Clay Prim independently discovered it in $1957$, and in $1959$ it was rediscovered once more by Edsger Wybe Dijkstra.

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

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Prim's algorithm
• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): tree
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Prim's algorithm
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): tree
• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Prim's algorithm