- Step 2: Choose an edge $e$ of $G$ such that:
- Step 3: Add $e$ to $T$.
- Step 4: 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 3 is executed, which increases the number of edges in $T$ by 1.
- Step 1: Trivially definite.
- Step 2: As the edges of a graph can be arranged in order of weight, there is a definite edge (or set of edges) with minimal weight. It is straightforward to select an edge $e$ which does not make a cycle in $T$, by ensuring that at least one end of $e$ is incident to a vertex which has not so far been connected into $T$.
- Step 3: Trivially definite.
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.
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 Kruskal's greedy algorithm.
In this case, the greedy algorithm does produce the minimum spanning tree.
Source of Name
This entry was named for Joseph Bernard Kruskal.
- 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): $\S 4.1$: The Minimal Connector Problem: An Introduction to Trees
- 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): Entry: Kruskal's algorithm
- 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Entry: Kruskal's algorithm
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Entry: Kruskal's algorithm