Prims Minimum Spanning Tree (MST)

Introduction

This is one of the most commonly used greedy algorithms in many fields. This algorithm tries to make a minimum cost Tree out of a given connected graph, otherwise no tree would exist but a Forest. Following are some applications of Prim's algorithm. There can also be performed by using the Kruskal's algorithms. I'll be talking about the Kruskal's algorithm in a later post. You may also refer to the blog post http://binary-maths.blogspot.com/2015/05/minimal-network-euler-107.html for Kruskal's algorithms as well.

Let's see how it works.

Say we have a graph represented by the adjacency matrix as follows

Graph g = { {0, 2, I, 6, I},
                    {2, 0, 3, 8, 5},
                    {I, 3, 0, I, 7},
                    {6, 8, I, 0, 9},
                    {I, 5, 7, 9, 0},
                  }
where I stands for Infinity or non-edges.
Graph in pictorial view may look like this.

            2        3
      (0)----(1)----(2)
         |      /   \       |
       6| 8 /       \5   |7
         |  /           \   |
       (3)----------(4)
                 9

Algorithm

What happens in the algorithm is we take a vertex and try to set parent for each neighbour if that edge has a lesser cost than the one already have to visit that particular vertex. For an example from 0 we can set parents of 1 as 0 and 3 as 0 and so on. Eventually the algorithm will end up selecting minimum cost incident edge for each of the vertices.

To start with keep an array to save the minimum cost to incident on a given vertex. This array keeps track of the edge that has minimum cost to reach the vertex from all the valid neighbours. In the beginning the array would look like this. The value of index is the vertex id.

minTree = { I, I, I, I, I}

we maintain another array to store parent vertex's index and to check whether a given node is visited already.

The algorithm starts with any vertex say 0. So we make the minTree[0] as 0 and proceed.

Now out of the minTree array get the vertex with min value. Which is 0. Mark as visited by setting visited[0]=true. parent[1]=0, parent[3]=0, minTree[1]=2 (cost of incident edge) and minTree[3]=6. We continue untill there are no unvisited vertices. Ultimately our tree will lie in the parent array as index and value as the edge vertices of the MST.

Code

Feel free to visit the original repository of algorithms at:

URL https://github.com/anuradhawick/Algorithms