Kruskal's Algorithm

Kruskal’s Algorithm
Field: Graph Theory
Image Created By: Nordhr

Kruskal’s Algorithm

Kruskal’s Algorithm finds a minimum spanning tree in a connected graph with edge weights.

Basic Description

A minimum spanning tree (MST) is an acyclic sub-graph that connects all of the vertices in the graph with minimum total edge weight. This algorithm first sorts the edges by their edge weights. It adds each edge into the MST, starting with the one with the smallest weight, and after each addition checks to see if there is a cycle in the new tree. If there is a cycle, it removes the edge that it just added that made the cycle. Kruskal’s algorithm is guaranteed to find a minimum spanning tree, but it may not be the only MST possible for the graph.

A More Mathematical Explanation

Note: understanding of this explanation requires: *Graphs, Pointers, Running Time

[Click to view A More Mathematical Explanation]

The Pseudo Code

<span class="_togglegroup _toggle_initshow _toggle _toggler toggle-visible" style [...]

[Click to hide A More Mathematical Explanation]

The Pseudo Code

[show more][hide]

This pseudo code shows the procedure for Kruskal’s Algorithm more formally. The second ‘find’ function implements path compression to improve running time.

The Underlying Data Structure

[show more][hide]

Using a Tree

While the value X stores which edges have been added to the overall minimum spanning tree, we need an efficient way to check to see if there is a cycle in the subgraph X. One way to do this is using directed trees of vertices. They keep track of whether any vertices (specifically the two of the edge we are trying to add) are already in the same connected component. If they are, we know that adding the new edge will create a cycle.

Find

We start out as each vertex being its own connected component. Since there are no edges, no vertices can be connected to each other. In each of these trees, the root vertex is used as a name for the entire tree. As the algorithm progresses, each vertex points to a parent that is higher up in the tree, ending at the same root node. Each root node has itself as a parent. That way the ‘find’ function only needs to return the root vertex of the tree (for each vertex) to tell us if two vertices are in the same component. If and only if they are, the have the same root node.

Union by Rank

When adding a new edge to the MST, the two components on the end of the edge are not connected, but now need to be. To do this we use the ‘union by rank’ function. Each vertex in the tree has a rank (they start at 0), which is the height of the tree below the vertex. When two trees are merged, the root vertex of the tree with a higher rank becomes the root vertex of the new tree, and the root vertex of the tree with the lower rank sends its parent pointer to the new root. If the two roots have the same rank, an arbitrary one becomes the new root, and it has its rank incremented by one.

Path Compression

When we call ‘find’ on a certain vertex, the function works its way up the tree using parent pointers, starting at that vertex until it reaches the root. In the original find function it will have to do this every time find is called on that vertex. We can use a different version of find to make this process faster the next time ‘find’ is called on that vertex. When we call find on a vertex the first time, we can set its parent pointer to go directly to the root of the tree. This is called path compression. Although the root may change, we have still bypassed having to look at the nodes that we already have seen in the past every time find is called. When path compression is used, rank may no longer reflect the actual height of the subtree from that node, but it does set an upper bound.

Running Time

From looking through the algorithm, we can see that the first thing that happens is calling makeset() for each vertex. Translating this into running time we have $|V|*O(makeset())$. Next we sort the edges: $|E|*log(|E|)$. For each edge we have to call find on its two vertices, and then possibly call union. Thus the running time for this portion of code is $|E|*2*O(find())$. We know that we will only have to call union $|V-1|$ times, because after that all of the vertices are in the same set.

Makeset() only has to set the parent pointer and rank of the vertex, so it is a constant time operation.

The find() operation is a little more complicated. Because a rank k node is created by merging two trees that both have roots on rank k-1, we can say that there are at least 2^k nodes in a tree of rank k. Since all rank k nodes have at least 2^k descendants and no nodes of the same rank share descendants, we can say that there are no more than the total number of nodes over 2^k nodes of each rank k. This means that the tree's height is no greater than $log(|V|)$.

Other than calling find, union() is a constant time operation. Find is called twice, but because of the properties of running times, constants do not matter. The running time for union is therefore the same as the running time for find.

Putting it all together we have a running time of $O( |V| + |E|*log(|E|) + |E|*log(|V|) + |V|*log(|V|))$. In an undirected graph there are at most $|V^{2}-1|$ edges, so E can be reduced to $O(|V^{2}|)$. Also, log(x²) can be reduced to 2*log(x), which is just log(x). This gives us a running time of $O(|V^{2}|log(|V|))$.

Here we can see that find() and the initial sorting are the bottle neck of this running time. But what if the edges are already sorted by edge weights? We already know that we can improve the find function's running time with path compression. The value log*(n) is defined as how many times you must take the log of a number for it to be less than or equal to 1. log* time is essentially constant because log*(x) is only more than 5 if x > 2⁶⁵⁵³⁶. Using path compression, the running time of find is $O(|V|*log*(|V|))$. So if our edges are already sorted, this makes the running time of the entire algorithm essentially linear.

Why it works

When each edge is added, to comply with the cut property, it must be the least weighted edge that connects two components that are otherwise not connected. Since the algorithm tries to add the edge with the lowest possible weight, it cannot break the first requirement. Also, if the components were connected already, there will be a cycle and the algorithm will not add the edge to the MST. We know that the edge that is already connecting the components has a smaller weight, because it was added first.

Why It's Interesting

Minimum spanning trees can be useful in networking. In this case one wants all of the computers or phone lines to be connected to one another, but at a minimal cost. The weights on the edges therefore can represent a maintenance cost or usage time, whatever is being optimized.

Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

Related Links

Additional Resources

Wikipedia's Article

Rashid Muhammad's Page

References

---

If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.