Prim's Algorithm
This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code. |
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 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
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Prim's algorithm