Kruskal's Algorithm

This algorithm creates a forest of trees. Initially the forest consists of n single node trees (and no edges). At each step, we add one (the cheapest one) edge so that it joins two trees together. If it were to form a cycle, it would simply link two nodes that were already part of a single connected tree, so that this edge would not be needed.

The basic algorithm looks like this:

Forest MinimumSpanningTree( Graph g, int n, double **costs ) {
   Forest T;
   Queue q;
   Edge e;
   T = ConsForest( g );
   q = ConsEdgeQueue( g, costs );
   for(i=0;i<(n-1);i++) {
       do {
          e = ExtractCheapestEdge( q );
       } while ( Cycle( e, T ) );
       AddEdge( T, e );
   }
   return T;
}

The steps are:

  1. Construct a forest - with each node in a separate tree.
  2. Place the edges in a priority queue.
  3. Until we've added n-1 edges,
    1. Continue extracting the cheapest edge from the queue,
      until we find one that does not form a cycle,
    2. Add it to the forest. Adding it to the forest will join two trees together.

Every step joins two trees in the forest together, so that, at the end, only one tree will remain in T.

We can use a heap for the priority queue. The trick here is to detect cycles. For this, we need a union-find structure.

Union-find structure

To understand the union-find structure, we need to look at a partition of a set.

Partitions

A partitions is a set of sets of elements of a set.

  • Every element of the set belong to one of the sets in the partition.
  • No element of the set belong to more than one of the sub-sets.

or

  • Every element of a set belongs to one and only one of the sets of a partition.

The forest of trees is a partition of the original set of nodes. Initially all the sub-sets have exactly one node in them. As the algorithm progresses, we form a union of two of the trees (sub-sets), until eventually the partition has only one sub-set containing all the nodes.

A partition of a set may be thought of as a set of equivalence classes. Each sub-set of the partition contains a set of equivalent elements (the nodes connected as one of the trees of the forest). This notion is the key to the cycle detection algorithm. For each sub-set, we denote one element as the representative of that sub-set or equivalence class. Each element in the sub-set is, somehow, equivalent and represented by the nominated representative.

As we add elements to a tree, we arrange that all the elements point to their representative. As we form a union of two sets, we simply set the representative of one of the sets to point to any element of the other set.

So the test for a cycle reduces to: for the two nodes at the ends of the candidate edge, find their representatives. If the two representatives are the same, the two nodes are already in a connected tree and adding this edge would form a cycle. The search for the representative simply follows a chain of links.

Each node will need a representative pointer. Initially, each node is its own representative, so the pointer is set to NULL. As the initial pairs of nodes are joined to form a tree, the representative pointer of one of the nodes is made to point to the other, which becomes the representative of the tree. As trees are joined, the representative pointer of the representative of one of them is set to point to any element of the other. (Obviously, representative searches will be somewhat faster if one of the representatives is made to point directly to the other.)

Select diagrams of Kruskal's algorithm in operation.

Greedy operation

At no stage did we try to look ahead more than one edge - we simply chose the best one at any stage. Naturally, in some situations, this myopic view would lead to disaster! The simplistic approach often makes it difficult to prove that a greedy algorithm leads to the optimal solution. proof by contradiction is a common proof technique used: we demonstrate that if we didn't make the greedy choice now, a non-optimal solution would result. Proving the MST algorithm
is, happily, one of the simpler proofs by contradiction!

Data structures for graphs

You should note that we have discussed graphs in an abstract way: specifying that they contain nodes and edges and using operations like AddEdge, Cycle, etc. This enables us to define an abstract data type without considering implementation details, such as how we will store the attributes of a graph! This means that a complete solution to, for example, the MST problem can be specified before we've even decided how to store the graph in the computer. However, representation issues can't be deferred forever, so we need to examine ways of representing graphs in a machine. As before, the performance of the algorithm will be determined by the data structure chosen.

The following sequence of diagrams illustrates Kruskal's algorithm in operation.

Step 1: the example graph with vertices a to i and weighted edges; the shortest edge gh (weight 1) is added, g is the representativegh is shortest.

Either g or h could be the representative,
g chosen arbitrarily.

Step 2: edge ci (weight 2) is added, giving a second tree with representative cci creates two trees.

c chosen as representative for second.

Step 3: edge fg (weight 2) is added to the tree of gfg is next shortest.

Add it, choose g as representative.

Step 4: edge ab (weight 4) is added, creating a third treeab creates a 3rd tree
Step 5: edge cf (weight 4) is added, merging the trees of c and g, with c as representativeAdd cf,
merging two trees.

c is chosen as the representative.

Step 6: edge gi (weight 6) is rejected because g and i already have the same representative cgi is next cheapest,
but a cycle would be created.

c is the representative of both.

Step 7: edge cd (weight 7) is added insteadAdd cd instead
Step 8: edge hi (weight 7) is rejected because it would make a cyclehi would make a cycle
Step 9: edge ah (weight 8) is added instead, joining the tree of a and b to the main treeAdd ah instead
Step 10: edge bc would create a cycle, so de (weight 9) is added, completing the minimum spanning treebc would create a cycle.

Add de instead
to complete the spanning tree -
all trees joined, c is sole representative.

Where Kruskal's algorithm is used

A minimum spanning tree answers "connect all of these, as cheaply as possible, with no redundant links". That is a real question in a surprising number of fields, and Kruskal's version — sort the edges, add the cheapest that does not close a cycle — is the one to reach for when the graph is sparse and already held as a list of edges.

  • Network and infrastructure design. The original motivation: laying cable, pipeline, road or power line to link a set of sites at least total cost. Circuit and chip layout use it the same way.
  • Clustering. Stop Kruskal early and the components it has built are the clusters; equivalently, build the whole tree and delete the k − 1 most expensive edges to get k groups. This is single-linkage hierarchical clustering, and the MST is the whole computation.
  • Image segmentation. The Felzenszwalb-Huttenlocher algorithm treats pixels as vertices and runs what is essentially Kruskal with a predicate deciding whether two regions should merge.
  • Approximation algorithms. A minimum spanning tree gives a 2-approximation for the metric travelling salesman problem, and is the first step of the better Christofides approximation.
  • Phylogenetics and taxonomy, building trees of relatedness from a matrix of distances, and handwriting and shape recognition, where strokes are linked into a minimal structure.

Kruskal or Prim? They produce the same weight (the same tree, if all edge weights are distinct) and differ in shape of work. Kruskal sorts all the edges and uses union-find, which suits a sparse graph given as an edge list, and parallelises reasonably. Prim grows a single tree with a priority queue, which suits a dense graph given as an adjacency matrix.