# minimum spanning tree Kruskal’s algorithm

*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.
*

*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?*

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

*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 **

**(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:
*

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 |
#include<iostream> #include<vector> #include<algorithm> using namespace std; #define edge pair<int,int> class Graph { private: vector<pair<int, edge > > G; // graph vector<pair<int, edge > > T; // mst int *parent; int V; // number of vertices/nodes in graph public: Graph(int V); void AddEdgeAndWeight(int u, int v, int weight); int find_set(int i); void union_set(int u, int v); void kruskal(); void print(); }; Graph::Graph(int V) { parent = new int[V]; //i 0 1 2 3 4 5 //parent[i] 0 1 2 3 4 5 for (int i = 0; i < V; i++) parent[i] = i; G.clear(); T.clear(); } void Graph::AddEdgeAndWeight(int u, int v, int weight) { // reset graph and mst G.push_back(make_pair(weight, edge(u, v))); } int Graph::find_set(int i) { // If i is the parent of itself if (i == parent[i]) 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 find_set(parent[i]); } void Graph::union_set(int u, int v) { parent[u] = parent[v]; } void Graph::kruskal() { int i, uRep, vRep; sort(G.begin(), G.end()); // increasing weight for (i = 0; i < G.size(); i++) { uRep = find_set(G[i].second.first); vRep = find_set(G[i].second.second); if (uRep != vRep) { T.push_back(G[i]); // add to tree union_set(uRep, vRep); } } } void Graph::print() { cout << "Edge :" << " Weight" << endl; for (int i = 0; i < T.size(); i++) { cout << T[i].second.first << " " << T[i].second.second << " " << T[i].first; cout << endl; } } int main() { Graph g(6); g.AddEdgeAndWeight(0, 1, 4); g.AddEdgeAndWeight(0, 2, 4); g.AddEdgeAndWeight(1, 2, 2); g.AddEdgeAndWeight(1, 0, 4); g.AddEdgeAndWeight(2, 0, 4); g.AddEdgeAndWeight(2, 1, 2); g.AddEdgeAndWeight(2, 3, 3); g.AddEdgeAndWeight(2, 5, 2); g.AddEdgeAndWeight(2, 4, 4); g.AddEdgeAndWeight(3, 2, 3); g.AddEdgeAndWeight(3, 4, 3); g.AddEdgeAndWeight(4, 2, 4); g.AddEdgeAndWeight(4, 3, 3); g.AddEdgeAndWeight(5, 2, 2); g.AddEdgeAndWeight(5, 4, 3); g.kruskal(); g.print(); return 0; } |

1 |
Output: |

1 2 3 4 5 6 |
Edge : Weight 1 2 2 2 5 2 2 3 3 3 4 3 0 1 4 |

*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

## Leave a Reply