minimum spanning tree definition: What is minimum spanning tree

Kruskal’s algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted undirected graph. A minimum spanning tree of a connected undirected graph is a tree which connects all the vertices and sum of weights of all the edges of minimum spanning tree is smallest compare to all other trees in a given graph.

Note: we can see that in the let side the minimum spanning tree has less than (n -1) edges, where n is number of vertices. Look at below figure which explains the Kruskal’s algorithm steps.

krusk

C++ implementation of above Kruskal’s algorithm

Basically, we have to build minimum spanning tree of the graph by adding the smallest weighted edge into the minimum spanning tree that doesn’t form a cycle.

But there is one question?

How will you find possibility of forming a cycle during adding an edge to previously selected edge?

conf

Ok Let us use Union-Find Disjoint- set data structure. Look at the below figure.

unf

 From above figure it is clear that two different trees are having different parents, i mean representatives. like for right side tree (1-2-3-4) 1 is representative while in left side tree ( 4-0-6) 4 is representative, these  1 and 4 are just like id of these trees. Let us look at left side tree if vertex 5 and vertex 3 will be connected they will make tree to form a cycle. So to prevent a tree to form a cycle, we can check whether an edge of vertices have same root ( representative ) ,if they have same representative then they will form a cycle.

Each tree is a disjoint set. If two elements are in the same tree, then they are in the same disjoint set. The root node (or the topmost node) of each tree is called the representative of the set. There is always a single unique representative of each set. ( source: http://www.mathblog.dk/disjoint-set-data-structure/)

There are two operation is performed on disjoint-set data structure.

(1) Find

// Finds the representative of the set that i is an element of
int f ind( int i) {
     // If i is the parent of itself
     if (parent[i] == i) {
         // Then i is the representative of his set
         return i;
     }
     else { // Else if i is not the parent of itself
         // Then i is not the representative of his set,
         // so we recursively call Find on its parent
         return f ind(parent[i]);
     }
}

(2) Union

Here union operation means merging two trees. The one tree will be under the root node of  other tree. In this way the new tree will have one Representative or id. we can do this by ( if u and v are two vertex of an edge ).

int pu = find(u);

int pv = find( v);

parent[pu] = parent[pv];  // link

Here is complete code for Kruskal’s algorithm based on union find for below graph:

mstk

 

This code has complexity of  O(ELogE + ELogV) time.

Ref: //http://stackoverflow.com/questions/1195872/kruskal-vs-prim

http://zobayer.blogspot.in/2010/01/kruskals-algorithm-in-c.html

Disjoint-set data structure