Kruskal's Algorithm

From ProofWiki
Jump to navigation Jump to search


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:


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.


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.


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.

Also see