Minimum Spanning Trees and Kruskal’s Algorithm implemented in Rust.

In this story we are going to look at the famous algorithm of Kruskal to find a minimum spanning tree in a connected graph.

Remember, a tree is a connected graph without cycles. A spanning tree of a graph G is a sub-graph of G that is a tree and contains all vertexes of G. A weighted graph is a graph together with a function w assigning to each edge a non-negative real number (“weight”). A minimum spanning tree in a weighted graph is a spanning tree T such that the sum \sum_{e in T} w(e) is minimal. That is, edges of a minimum spanning tree are chosen that way, that their sum of values assigned by w is the smallest among all other spanning trees. You may find an introduction into basic concepts of graph theory here.

Algorithm:

The algorithm is described as follows:

1. Start with an empty set of edges.
2. Consider all the edges that do not produce a cycle when being added to the set. Pick the one with smallest weight and add it to the set.
3. Repeat #2 until no further edges can be added without producing a cycle.

Obviously, the resulting set of edges produces a tree that contains all the vertexes from G. Let us sketch the proof why indeed it produces one of minimum weight.