Kruskal’s Algorithm

Kruskal’s algorithm was discovered in 1956 by Joesph Kruskal. However, it’s almost identical to an earlier algorithm, called Borůvka’s algorithm, which was discovered by Otakar Borůvka in 1926.

A different growing strategy

Kruskal’s algorithm, like Prim’s algorithm, is an algorithm for finding minimum spanning trees. It begins with a collection of $n$ isolated vertices—each vertex, by itself, a tree.

In each round of Kruskal’s algorithm, an edge is added between two vertices in a way that brings two of the trees together into a single bigger tree. Each step leads to a smaller collection of trees. Kruskal’s algorithm essentially grows a tree out of a forest.

The central idea

To find an MST of a connected graph $G$,

1. Start with a forest $F$ consisting of $n$ components, each containing exactly one vertex.

2. At each step, add an edge $e$ between two vertices of $F$ that meets the following criteria:

   • The edge $e$ has minimum weight among all edges of $G$ that are not already in $F$.

   • The end-vertices of $e$ belong to different components of $F$.

   This second criterion ensures that, at each step, $F$ remains acyclic.

The edge addition at each step reduces the number of components by one. So, once $n−1$ edges have been added, $F$ consists of just a single component.

Once all edges have been considered, the algorithm must terminate.

After the last round is finished, $F$ is acyclic, connected, and contains all vertices of $G$. Therefore, by definition, $F$ is a spanning tree of $G$. We’ll see later why this spanning tree is a minimum spanning tree.

Visualization

Let’s see this in action before we fill out the details.

Let’s look at the bookkeeping required to implement the algorithm.

Implementation details

To check if an edge addition to $F$ creates a cycle, we want to keep track of the vertices belonging to each connected component. For this, we represent the connected components of $F$ as disjoint setsdisjoint of vertices, with support for the following types of operations:

Disjoint-set data structure

The disjoint-set data structure (also known as the union-find data structure) is a nifty data structure that satisfies these requirements. We assume the disjoint-set data structure used by our algorithms supports the following methods:

• DisjointSet(v): Creates a set containing the vertex v.

• Find(v): Returns the name of the set containing the vertex v.

• Union(x, y): Returns union of sets named x and y.

A set receives the name of one of its member vertices. When different sets are merged, the name of the set may change to the name of a different vertex.

We discuss this data structure in greater detail in the next lesson.

Algorithm

There is more than one way to represent a minimum-spanning tree. Here, we just represent the minimum spanning tree as a simple collection $S$ of edges that constitute that minimum spanning tree.

Running time

The running time of Kruskal’s algorithm depends on the choice and implementation of the data structure.