Having seen a variety of algorithms for shortest paths on weighted graphs, we now move to a completely different problem that of computing, what is called Minimum Cost Spanning Tree.

So, to motivate the problem, let us consider the following example. Suppose, we are in a district which has a road network and after a bad cyclone, the roads are all being damaged. So, the first priority of the government is to restore the roads, so that relief can be sent to various parts of the district and also people can start moving around again. So, the priority is to restore enough roads, so that everybody can move around. So, the first criteria for the government to restore road is to ensure connectivity. So, given this which set of roads should the government restore first?

So, if the main criterion is minimum connectivity, then it should be clear that there is no point in restoring roads which find a loop. For instance, supposing we restore all these four roads, then we could have deleted any one of these roads, say 3 to 4 or 2 to 3 and still one can get from any of these four towns to any four other towns in the district. So, removing an edge from a loop cannot disconnect a graph and our aim is to find some sub set of edges within this graph which are connected in such a way that this is a minimal such set of edges.

So, what we want is a connected sub graph of this original graph which does not have any loops which is acyclic and this is precisely what is called a tree.

So, tree by definition is a connected acyclic graph. And in particular, we start to the arbitrary graph and we are looking for a tree which sits inside the graph, which is a sub graph in terms of the number of the edges, which connects all the vertices in the original graph. So, such a tree is called a spanning tree, it spans the vertices of the original graph, but it forms a tree outer the sub set of three edges.

Now, suppose that the graph also has weights. In this example, the weight for instance could be the cost of repairing a road. So, supposing restoring the road has a cost and now the government would like to not only restore connectivity, but do it I mean at minimum cost. So, if for instance, the government chose to repair this tree of roads, then the total cost is 18 plus 6, 24 plus 70, 94 plus 20, 114. So, it could incur cost of 114 to the store, this spanning tree.

On the other hand, if the government chooses green spanning tree, then the cost reduces to 10 plus 6 is16 plus 20 is 36 plus 8 is 44. So, different spanning trees now will come at different cost and the goal would be to reduce the cost per minimum.

So, before we move ahead to algorithms to compute minimum cost spanning trees, let us look at some basic facts about trees. So, remember that by definition, a tree is a connected acyclic graph. So, the graph in general will have n vertices, so the claim is that any tree has exactly n minus 1 edges.

Now, if I take a tree and then I add an edge, it must create a cycle, we already saw this in this previous argument that we said, so supposing I have a tree, so a tree in general looks something like this. So, it is a graph, it has a kind of more cycles, but many things branching out. Now, if anywhere if I create a tree, supposing I add them and supposing I take some i there and some j here, we may decide to add an edge. So, we know that because it is a tree, there is already connection. So, there is some path which in this case to this vertex from i to j. So, therefore, that path p plus this edge forms acyclic.

So, another consequence of all these definitions is that between any two paths, any two vertices in a tree, there can only be one unique path. So, supposing there are actually two paths, so let us look at two vertices, here we have drawn them as i and j and suppose there are two parts. So, if I follow the two parts, then it is very clear that because there are two different ways are going there, there will be some loops somewhere in between.

So, our target right now is to build a minimum cost spanning tree. So, there are two naturally greedy strategies that one can think of. One is, since you are looking for a minimum cost tree to start with this smallest stage and incrementally build the tree. So, we keep adding edges to the existing tree, so that the new graph remains a tree and it grows as little as possible in terms of cost. This will give raise to an algorithm which is called prim’s algorithm. It will also turn out to be very similar to Dijkstra’s shortest path algorithm with a single source.