{"id":27533,"date":"2018-02-06T20:56:45","date_gmt":"2018-02-06T15:26:45","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27533"},"modified":"2018-02-06T20:56:45","modified_gmt":"2018-02-06T15:26:45","slug":"kruskals-minimum-spanning-tree-using-stl-c","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/kruskals-minimum-spanning-tree-using-stl-c\/","title":{"rendered":"Kruskal\u2019s Minimum Spanning Tree using STL in C++"},"content":{"rendered":"

Given an undirected, connected and weighted graph, find M<\/strong>inimum S<\/strong>panning T<\/strong>ree (MST) of the graph using Kruskal\u2019s algorithm.<\/p>\n

\"Kruskal\u2019s<\/p>\n

Input :   Graph as an array of edges\r\nOutput :  Edges of MST are \r\n          6 - 7\r\n          2 - 8\r\n          5 - 6\r\n          0 - 1\r\n          2 - 5\r\n          2 - 3\r\n          0 - 7\r\n          3 - 4\r\n          \r\n          Weight of MST is 37\r\n\r\nNote : <\/strong> There are two possible MSTs, the other\r\n        MST includes edge 1-2 in place of 0-7.<\/pre>\n
We have discussed below Kruskal\u2019s MST implementations.<\/p>\n
Greedy Algorithms | Set 2 (Kruskal\u2019s Minimum Spanning Tree Algorithm)<\/p>\n
Below are the steps for finding MST using Kruskal\u2019s algorithm<\/p>\n
    \n
  1. Sort all the edges in non-decreasing order of their weight.<\/li>\n
  2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.<\/li>\n
  3. Repeat step#2 until there are (V-1) edges in the spanning tree.<\/li>\n<\/ol>\n
    Here are some key points which will be useful for us in implementing the Kruskal\u2019s algorithm using STL.<\/p>\n
      \n
    1. Use a vector of edges which consist of all the edges in the graph and each item of a vector will contain 3 parameters: source, destination and the cost of an edge between the source and destination.\n
      vector<pair<int, pair<int, int> > > edges;<\/pre>\n
      Here in the outer pair (i.e pair<int,pair<int,int> > ) the first element corresponds to the cost of a edge while the second element is itself a pair, and it contains two vertices of edge.<\/li>\n
    2. Use the inbuilt std::sort to sort the edges in the non-decreasing order; by default the sort function sort in non-decreasing order.<\/li>\n
    3. We use the Union Find Algorithm to check if it the current edge forms a cycle if it is added in the current MST. If yes discard it, else include it (union).<\/li>\n<\/ol>\n
      Pseudo Code:<\/strong><\/p>\n
      \/\/ Initialize result\r\nmst_weight = 0\r\n\r\n\/\/ Create V single item sets\r\nfor<\/strong> each<\/strong> vertex v\r\n\tparent[v] = v;\r\n\trank[v] = 0;\r\n\r\nSort<\/strong> all edges into non decreasing \r\norder by weight w\r\n\r\nfor<\/strong> each (u, v) taken from the sorted list  E\r\n    do if<\/strong> FIND-SET<\/strong>(u) != FIND-SET<\/strong>(v)\r\n        print<\/strong> edge(u, v)\r\n        mst_weight += weight of edge(u, v)\r\n        UNION<\/strong>(u, v)<\/pre>\n
      Below is C++ implementation of above algorithm.<\/p>\n
       
       <\/div> 
      \/\/ C++ program for Kruskal's algorithm to find Minimum\/\/ Spanning Tree of a given connected, undirected and\/\/ weighted graph#include<bits\/stdc++.h>using namespace std; \/\/ Creating shortcut for an integer pairtypedef  pair<int, int> iPair; \/\/ Structure to represent a graphstruct Graph{    int V, E;    vector< pair<int, iPair> > edges;     \/\/ Constructor    Graph(int V, int E)    {        this->V = V;        this->E = E;    }     \/\/ Utility function to add an edge    void addEdge(int u, int v, int w)    {        edges.push_back({w, {u, v}});    }     \/\/ Function to find MST using Kruskal's    \/\/ MST algorithm    int kruskalMST();}; \/\/ To represent Disjoint Setsstruct DisjointSets{    int *parent, *rnk;    int n;     \/\/ Constructor.    DisjointSets(int n)    {        \/\/ Allocate memory        this->n = n;        parent = new int[n+1];        rnk = new int[n+1];         \/\/ Initially, all vertices are in        \/\/ different sets and have rank 0.        for (int i = 0; i <= n; i++)        {            rnk[i] = 0;             \/\/every element is parent of itself            parent[i] = i;        }    }     \/\/ Find the parent of a node 'u'    \/\/ Path Compression    int find(int u)    {        \/* Make the parent of the nodes in the path           from u--> parent[u] point to parent[u] *\/        if (u != parent[u])            parent[u] = find(parent[u]);        return parent[u];    }     \/\/ Union by rank    void merge(int x, int y)    {        x = find(x), y = find(y);         \/* Make tree with smaller height           a subtree of the other tree  *\/        if (rnk[x] > rnk[y])            parent[y] = x;        else \/\/ If rnk[x] <= rnk[y]            parent[x] = y;         if (rnk[x] == rnk[y])            rnk[y]++;    }};  \/* Functions returns weight of the MST*\/ int Graph::kruskalMST(){    int mst_wt = 0; \/\/ Initialize result     \/\/ Sort edges in increasing order on basis of cost    sort(edges.begin(), edges.end());     \/\/ Create disjoint sets    DisjointSets ds(V);     \/\/ Iterate through all sorted edges    vector< pair<int, iPair> >::iterator it;    for (it=edges.begin(); it!=edges.end(); it++)    {        int u = it->second.first;        int v = it->second.second;         int set_u = ds.find(u);        int set_v = ds.find(v);         \/\/ Check if the selected edge is creating        \/\/ a cycle or not (Cycle is created if u        \/\/ and v belong to same set)        if (set_u != set_v)        {            \/\/ Current edge will be in the MST            \/\/ so print it            cout << u << " - " << v << endl;             \/\/ Update MST weight            mst_wt += it->first;             \/\/ Merge two sets            ds.merge(set_u, set_v);        }    }     return mst_wt;} \/\/ Driver program to test above functionsint main(){    \/* Let us create above shown weighted       and unidrected graph *\/    int V = 9, E = 14;    Graph g(V, E);     \/\/  making above shown graph    g.addEdge(0, 1, 4);    g.addEdge(0, 7, 8);    g.addEdge(1, 2, 8);    g.addEdge(1, 7, 11);    g.addEdge(2, 3, 7);    g.addEdge(2, 8, 2);    g.addEdge(2, 5, 4);    g.addEdge(3, 4, 9);    g.addEdge(3, 5, 14);    g.addEdge(4, 5, 10);    g.addEdge(5, 6, 2);    g.addEdge(6, 7, 1);    g.addEdge(6, 8, 6);    g.addEdge(7, 8, 7);     cout << "Edges of MST are \\n";    int mst_wt = g.kruskalMST();     cout << "\\nWeight of MST is " << mst_wt;     return 0;}<\/code><\/pre> <\/div>\n
      Output :<\/strong><\/p>\n
      Edges of MST are \r\n          6 - 7\r\n          2 - 8\r\n          5 - 6\r\n          0 - 1\r\n          2 - 5\r\n          2 - 3\r\n          0 - 7\r\n          3 - 4\r\n          \r\n          Weight of MST is 37<\/pre>\n","protected":false},"excerpt":{"rendered":"
      Kruskal\u2019s Minimum Spanning Tree using STL in C++ – STL Implementation of Algorithms – Use a vector of edges which consist of all the edges in the graph.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[81350,81360],"tags":[81743,70802,71248,70796,70799,81745,70769,70783,70784,70774,81746,70794,70781,70772,70789,70785,70801,70771,81744],"class_list":["post-27533","post","type-post","status-publish","format-standard","hentry","category-graph","category-stl-implementation-of-algorithms","tag-c-program-to-implement-minimum-spanning-tree-using-kruskal-algorithm","tag-complexity-of-kruskal-algorithm","tag-difference-between-prims-and-kruskal-algorithm","tag-kruskal","tag-kruskal-algo","tag-kruskal-algorithm-c-adjacency-matrix","tag-kruskal-algorithm-example","tag-kruskal-algorithm-in-c","tag-kruskal-program-in-c","tag-kruskals-algorithm-c","tag-kruskals-algorithm-c-disjoint-set","tag-kruskals-algorithm-example","tag-kruskals-algorithm-in-c","tag-kruskals-algorithm-minimum-spanning-tree","tag-kruskals-algorithm-pdf","tag-prims-algorithm-in-c","tag-prims-and-kruskal-algorithm","tag-time-complexity-of-kruskal-algorithm","tag-write-a-program-for-minimum-spanning-trees-using-kruskals-algorithm"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27533","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27533"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27533\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27533"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27533"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27533"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}