Introduction to Minimum Spanning Tree

Minimum Spanning Tree

For this article, we are motivated by the problem of trying to find a Minimum Spanning Tree for a given graph as efficiently as possible. One might ask what is a Minimum Spanning Tree? Firstly, recall the definition of a graph in Graph Introduction. A Minimum Spanning Tree is a tree with overall minimum weight generated from a graph that includes every node in the original graph. You will recall that a tree is defined as a graph with n - 1 edges, n nodes, as well as no cycles throughout the tree. We can essentially think of it as generating the tree with smallest total weight by selecting edges from a graph.

Intuition

The main solution involves always picking the smallest weighted edge to greedily generate the tree. We will give some informal proofs or intuition for why these algorithms work in the sections below. Those interested can seek out a formal mathematical proof that a greedy solution can work to generate Minimum Spanning Trees from a graph but for now we will just accept our informal proof is true and assume that the solution works. This article will outline 2 main ways of computing Minimum Spanning Tree. The first will be through using Kruskal's algorithm, and the second will be through Prim's algorithm.

In most cases, the algorithm can be used interchangeably, so you likely only need to learn one of these algorithms for interviews.

Kruskal's Algorithm

Kruskal's algorithm generates the Minimum Spanning Tree by always choosing the smallest weighted edge in the graph and consistently growing the tree by one edge. The algorithm does the following,

1. We sort the edges from lowest to highest using any method(Priority Queue, built-in sorting algorithms etc.)
2. We then try every edge, as long as the 2 nodes that the edge connects are not currently connected by some path we then add the new edge to our graph.
3. Repeat step 2. until we have connected n - 1 edges then this process terminates.

Here is a graphic to illustrate this idea,