- Step 1: Choose any vertex of $G$, and add it to $T$.
- Step 3: If $T$ spans $G$, stop. Otherwise, go to Step 2.
The above constitutes an algorithm, for the following reasons:
For each iteration through the algorithm, step 2 is executed, which increases the number of edges in $T$ by 1.
- 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.
The input to this algorithm is the weighted graph $G$.
The output to this algorithm is the minimum spanning tree $T$.
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.
For these reasons it is also known as the DJP Algorithm, the Jarník Algorithm, or the Prim-Jarník Algorithm.
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Entry: Prim's algorithm