Kruskal's Algorithm

Algorithm

The purpose of this algorithm is to produce a minimum spanning tree for any given weighted graph $G$.

Step 1: Start with the edgeless graph $T$ whose vertices correspond with those of $G$.

Step 2: Choose an edge $e$ of $G$ such that:

a): Adding $e$ to $T$ would not make a cycle in $T$;

b): $e$ has the minimum weight of all the edges remaining in $G$ that fulfil the condition in a).

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:

Finiteness

For each iteration through the algorithm, step 3 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 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.

Step 4: 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.

Note

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.

Also see

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

Sources

• 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): Kruskal's algorithm
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): Kruskal's algorithm
• 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): Kruskal's algorithm