Prim's Algorithm

From ProofWiki
Jump to navigation Jump to search

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.


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


Also known as

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


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.


Also see


Sources