Minimum cost spanning trees | Kruskal’s Algorithms

Minimum cost spanning trees

1. A spanning tree of a graph is just a sub graph that contains all the vertices and is a tree.
2. Thus a spanning tree spans over all vertices of the graph
3. A minimum cost spanning tree of a weighted graph is a spanning tree of the graph with minimum total weight
4. Let G=(V,E) be a connected, undirected graph. For each edge (u,v)∈E, we have a weight w(u,v) specifying the cost to connect u and v. We wish to find an acyclic subset T ⊆ E that connects all of the vertices and whose total weight is minimized.
5. This problem can be solved by Greedy method
6. At each step we determine an edge (u,v) that can be added into a solution vector in such a way that the subset formed in A will give a Minimum Spanning Tree with minimum weight.
7. The each edge collected at A is called safe edge.
8. Two algorithms widely used for Minimum cost spanning trees are:
   1. Kruskal’s Algorithm       
   2. Prim’s Algorithm

Minimum cost spanning trees using Kruskal’s Algorithm

1. Edges of the graph are sorted in non-decreasing order by weight
2. Edges are considered one at a time for inclusion into a tree T
3. If adding an edge (v, w) to T would create a cycle then discard (v, w)  else add (v, w) to T .
   T may not be a tree at all stages in the algorithm. In fact, it will be a forest of trees
4. Disjoint sets are widely used to implement this algorithm. By applying UNION and FIND algorithms we can construct the Minimum Spanning TreeExample:

                                               Total Cost = 105

5.An algorithm for generating minimum cost spanning tree is given below:

Algorithm MST_Kruskal(G, w)
{
A:=φ;
for each vertex v ∈V [G] do
MAKE-SET(v);
mincost:=0;
//sort the edge of E by nondecreasing weight w;
for each edge (u,v ) ∈E do
{
if (FIND_SET(u) ≠ FIND_SET(v)) then
A:= A∪{(u,v )}
UNION(u, v);
mincost := mincsot + cost[u,v];
}
return mincost;
}

6.Time Complexity of Kruskal’s Algorithm is O(E log E)

Topic : Minimum cost spanning trees | Kruskal’s Algorithms