Minimum Spanning Tree beginner's guide

7395

Greedy Graph Theory Minimum Spanning Tree Career

Through this guide I will try to explain Minimum Spanning Trees (MST) in a beginner friendly way. I will go over Prim’s algorithm for finding MST. If people find this guide is helpful, I will extend it to add Kruskal’s algorithm as well. This is my first time writing a guide so please vote and comment your views on how I did! Thanks!

Minimum Spanning Tree (MST) is a spanning tree with least possible edge weight. What that means is that it is an undirected graph, where all the vertices are connected, with least possible edge weight, and no cycles. A weighted, undirected, and connected graph can have many spanning trees but only one MST.

Here is an image of a weighted, undirected, and connected graph. Blue edges are all the spanning trees of this graph and red edges are the minimum spanning tree (We will only use MST for all the future explanations in this guide.)

The total number of vertices, V in this Graph are 6. The total number of edges, E in an MST is (V-1) i.e. 6-1=5 edges. This is what the MST looks like for the above graph-

Alright, now that we have a basic understanding of how MST is supposed to be, let’s try and understand how to find a minimum spanning tree when given a graph!

Prim's Algorithm
Prim’s algorithm is a greedy algorithm. To find the MST using Prim’s, we pick an initial starting vertex and add it to a set. Then we grow the MST from that initial vertex by adding adjacent vertices one by one based on least value of edge weight.

Let’s create 2 disjoint (no common value) subsets of vertices, one is called StartSet and the other is called MstSet. StartSet is a key value pair with vertices and their distances from the adjacent vertix that has been added to the MstSet.
In the beginning, StartSet has all the vertices and MstSet has nothing.

StartSet: {(A, INF), (B, INF), (C, INF), (D, INF), (E, INF), (F, INF)}
MstSet: {}

Let’s pick a starting point. It doesn’t matter which one because MST is unique and no matter where you start, you are going to end up with the same tree.

I will begin at vertex C. From vertex C, we have the following paths-

Since we picked our starting point, let's add vertex C to MstSet and update it's value to 0 in StartSet (as it is our initial vertex and distant from a node to itself is 0.
Also update the values of vertices adjacent to C with their distances from C. Since A, D and E are adjacent to C, their values in StartSet are updated. Our subsets look as follows-

StartSet: {(A, 7), (B, INF), (C, 0), (D, 2), (E, 3), (F, INF)}
MstSet: {C}

From C, we can either pick A, D, or E as our next vertex.
Since the Prim's algorithm is Greedy, it will choose the path of least value i.e. the edge between C and D and will add vertex D to MstSet.

Next, the same process repeats with D. Update the value of vertices adjacent to D in StartSet. One thing to note here is that the distance of A from D is 6 which is less than distance of A from C. Therefore, in our subset StartSet, the value of A will update to 6 from 7. Same goes for E whose value will be updated from 3 to 1.
Let's look at the values in our subsets-

StartSet: {(A, 6), (B, 7), (C, 0), (D, 2), (E, 1), (F, INF)}
MstSet: {C, D}

So far we have C and D in our MST. Let's grow our MST some more by picking the next vertex.

Now our edge values are 6, 7 and 1. Since 1 is smallest, the next vertex to be added to the MstSet will be E. You can also look at our subsets and see that out of all the vertices that are currently not in MstSet, E has the least value.

Continuing our tradition of updating adjacent vertices in StartSet, B is updated to 5 and F is updated to 4.
Our subsets currently look like this-

StartSet: {(A, 6), (B, 5), (C, 0), (D, 2), (E, 1), (F, 4)}
MstSet: {C, D, E}

Now we may have a problem! The values of edges coming from E are 3, 4 and 5. Since 3 is smaller than the 2, ideally we should pick that. However, we can't do that because C is already in MstSet. So we will go a step further and pick the edge with value 4 i.e. the E-F edge.
Once again, add F to MstSet and update the adjacent vertices' values.

There is no change of values for vertices adjacent to F.
Let's take a quick look at our subsets after adding F.

StartSet: {(A, 6), (B, 5), (C, 0), (D, 2), (E, 1), (F, 4)}
MstSet: {C, D, E, F}

Now the only vertices that are not in MstSet are A and B. As you can see from the subset, between A and B, B has the smaller value (5). Also in the graph, the least value of edge weight to reach B is 5 (E-B edge) as compared to A which is 7 (F-A edge).

Therefore, we will go ahead and add B to our MstSet and update the values of it's adjacent vertices.
Value of A is updated to 3.
Our subsets look like this-

StartSet: {(A, 3), (B, 5), (C, 0), (D, 2), (E, 1), (F, 4)}
MstSet: {C, D, E, F, B}

Now, only A needs to be added. As we can see from both the graph and the subset, the least cost way to reach A is through A-B edge.

So, we will add A to our MstSet.
Let's look at the final values of our subsets-

StartSet: {(A, 3), (B, 5), (C, 0), (D, 2), (E, 1), (F, 4)}
MstSet: {C, D, E, F, B, A}

All the vertices have been added to the MstSet!
And finally, we have our Minimum Spanning Tree.

Now that you have seen me walk through Prim's algorithm, go ahead and check your understanding by starting at a different initial point and going through the graph! No matter where you begin, you will end up with this MST.

Here are some problems to practice MST with-

Thank you for reading through this guide. I hope it was helpful! Please let me know if you would like me to continue with MST and anything else you would like me to go over. Thank you for your time today!

Comments (7)