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.
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, 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 generates the Minimum Spanning Tree by always choosing the smallest weigthed edge in the graph and consistently growing the tree by one edge. The algorithm does the following,
- We sort the edges from lowest to highest using any method(Priority Queue, built-in sorting algorithms etc.)
- 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.
- Repeat step 2. until we have connected
n - 1edges then this process terminates.
Here is a graphic to illustrate this idea,