{"id":26347,"date":"2017-10-26T21:06:45","date_gmt":"2017-10-26T15:36:45","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26347"},"modified":"2017-10-26T21:06:45","modified_gmt":"2017-10-26T15:36:45","slug":"greedy-algorithms-set-2-kruskals-minimum-spanning-tree-algorithm","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-algorithm\/","title":{"rendered":"Greedy Algorithms | Set 2 (Kruskal\u2019s Minimum Spanning Tree Algorithm)"},"content":{"rendered":"

What is Minimum Spanning Tree?<\/em>
\nGiven a connected and undirected graph, a spanning tree<\/em> of that graph is a subgraph that is a tree and connects all the vertices together. <\/span>A single graph can have many different spanning trees. A minimum spanning tree (MST)<\/em> or minimum weight spanning tree for a weighted, connected and undirected graph is a spanning tree with weight less than or equal to the weight of every other spanning tree. The weight of a spanning tree is the sum of weights given to each edge of the spanning tree.<\/p>\n

How many edges does a minimum spanning tree has?<\/em>
\nA minimum spanning tree has (V \u2013 1) edges where V is the number of vertices in the given graph.<\/p>\n

What are the applications of Minimum Spanning Tree?<\/em>
\nSee this <\/a>for applications of MST.<\/p>\n[ad type=”banner”]\n

Below are the steps for finding MST using Kruskal\u2019s algorithm:<\/p>\n

1.<\/strong> Sort all the edges in non-decreasing order of their weight.\r\n\r\n2.<\/strong> Pick the smallest edge. Check if it forms a cycle with the spanning tree \r\nformed so far. If cycle is not formed, include this edge. Else, discard it.  \r\n\r\n3.<\/strong> Repeat step#2 until there are (V-1) edges in the spanning tree.<\/pre>\n
The step#2 uses Union-Find algorithm<\/a> to detect cycle. So we recommend to read following post as a prerequisite.
\nUnion-Find Algorithm | Set 1 (Detect Cycle in a Graph)<\/a>
\nUnion-Find Algorithm | Set 2 (Union By Rank and Path Compression)<\/a><\/p>\n
The algorithm is a Greedy Algorithm. The Greedy Choice is to pick the smallest weight edge that does not cause a cycle in the MST constructed so far. Let us understand it with an example: Consider the below input graph.<\/p>\n
\"Kruskal\u2019s<\/p>\n
The graph contains 9 vertices and 14 edges. So, the minimum spanning tree formed will be having (9 \u2013 1) = 8 edges.<\/p>\n
After sorting:\r\nWeight   Src    Dest\r\n1         7      6\r\n2         8      2\r\n2         6      5\r\n4         0      1\r\n4         2      5\r\n6         8      6\r\n7         2      3\r\n7         7      8\r\n8         0      7\r\n8         1      2\r\n9         3      4\r\n10        5      4\r\n11        1      7\r\n14        3      5<\/pre>\n
1.<\/strong> Pick edge 7-6:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
2.<\/strong> Pick edge 8-2:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
3.<\/strong> Pick edge 6-5:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
4.<\/strong> Pick edge 0-1:<\/em> No cycle is formed, include it<\/p>\n
\"Kruskal\u2019s<\/p>\n
5.<\/strong> Pick edge 2-5:<\/em> No cycle is formed, include it.<\/p>\n
6.<\/strong> Pick edge 8-6: <\/em>Since including this edge results in cycle, discard it.<\/p>\n
7.<\/strong> Pick edge 2-3:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
8.<\/strong> Pick edge 7-8:<\/em> Since including this edge results in cycle, discard it.<\/p>\n
9.<\/strong> Pick edge 0-7:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
10.<\/strong> Pick edge 1-2: <\/em>Since including this edge results in cycle, discard it.<\/p>\n
11.<\/strong> Pick edge 3-4:<\/em> No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
Java programming:<\/p>\n
 
 <\/div> 
\/\/ Java program for Kruskal's algorithm to find Minimum Spanning Tree\/\/ of a given connected, undirected and weighted graphimport java.util.*;import java.lang.*;import java.io.*; class Graph{    \/\/ A class to represent a graph edge    class Edge implements Comparable<Edge>    {        int src, dest, weight;         \/\/ Comparator function used for sorting edges based on        \/\/ their weight        public int compareTo(Edge compareEdge)        {            return this.weight-compareEdge.weight;        }    };     \/\/ A class to represent a subset for union-find    class subset    {        int parent, rank;    };     int V, E;    \/\/ V-> no. of vertices & E->no.of edges    Edge edge[]; \/\/ collection of all edges     \/\/ Creates a graph with V vertices and E edges    Graph(int v, int e)    {        V = v;        E = e;        edge = new Edge[E];        for (int i=0; i<e; ++i)            edge[i] = new Edge();    }     \/\/ A utility function to find set of an element i    \/\/ (uses path compression technique)    int find(subset subsets[], int i)    {        \/\/ find root and make root as parent of i (path compression)        if (subsets[i].parent != i)            subsets[i].parent = find(subsets, subsets[i].parent);         return subsets[i].parent;    }     \/\/ A function that does union of two sets of x and y    \/\/ (uses union by rank)    void Union(subset subsets[], int x, int y)    {        int xroot = find(subsets, x);        int yroot = find(subsets, y);         \/\/ Attach smaller rank tree under root of high rank tree        \/\/ (Union by Rank)        if (subsets[xroot].rank < subsets[yroot].rank)            subsets[xroot].parent = yroot;        else if (subsets[xroot].rank > subsets[yroot].rank)            subsets[yroot].parent = xroot;         \/\/ If ranks are same, then make one as root and increment        \/\/ its rank by one        else        {            subsets[yroot].parent = xroot;            subsets[xroot].rank++;        }    }     \/\/ The main function to construct MST using Kruskal's algorithm    void KruskalMST()    {        Edge result[] = new Edge[V];  \/\/ Tnis will store the resultant MST        int e = 0;  \/\/ An index variable, used for result[]        int i = 0;  \/\/ An index variable, used for sorted edges        for (i=0; i<V; ++i)            result[i] = new Edge();         \/\/ Step 1:  Sort all the edges in non-decreasing order of their        \/\/ weight.  If we are not allowed to change the given graph, we        \/\/ can create a copy of array of edges        Arrays.sort(edge);         \/\/ Allocate memory for creating V ssubsets        subset subsets[] = new subset[V];        for(i=0; i<V; ++i)            subsets[i]=new subset();         \/\/ Create V subsets with single elements        for (int v = 0; v < V; ++v)        {            subsets[v].parent = v;            subsets[v].rank = 0;        }         i = 0;  \/\/ Index used to pick next edge         \/\/ Number of edges to be taken is equal to V-1        while (e < V - 1)        {            \/\/ Step 2: Pick the smallest edge. And increment the index            \/\/ for next iteration            Edge next_edge = new Edge();            next_edge = edge[i++];             int x = find(subsets, next_edge.src);            int y = find(subsets, next_edge.dest);             \/\/ If including this edge does't cause cycle, include it            \/\/ in result and increment the index of result for next edge            if (x != y)            {                result[e++] = next_edge;                Union(subsets, x, y);            }            \/\/ Else discard the next_edge        }         \/\/ print the contents of result[] to display the built MST        System.out.println("Following are the edges in the constructed MST");        for (i = 0; i < e; ++i)            System.out.println(result[i].src+" -- "+result[i].dest+" == "+                               result[i].weight);    }     \/\/ Driver Program    public static void main (String[] args)    {         \/* Let us create following weighted graph                 10            0--------1            |  \\     |           6|   5\\   |15            |      \\ |            2--------3                4       *\/        int V = 4;  \/\/ Number of vertices in graph        int E = 5;  \/\/ Number of edges in graph        Graph graph = new Graph(V, E);         \/\/ add edge 0-1        graph.edge[0].src = 0;        graph.edge[0].dest = 1;        graph.edge[0].weight = 10;         \/\/ add edge 0-2        graph.edge[1].src = 0;        graph.edge[1].dest = 2;        graph.edge[1].weight = 6;         \/\/ add edge 0-3        graph.edge[2].src = 0;        graph.edge[2].dest = 3;        graph.edge[2].weight = 5;         \/\/ add edge 1-3        graph.edge[3].src = 1;        graph.edge[3].dest = 3;        graph.edge[3].weight = 15;         \/\/ add edge 2-3        graph.edge[4].src = 2;        graph.edge[4].dest = 3;        graph.edge[4].weight = 4;         graph.KruskalMST();    }}<\/code><\/pre> <\/div>\n
 <\/p>\n
Following are the edges in the constructed MST\r\n2 -- 3 == 4\r\n0 -- 3 == 5\r\n0 -- 1 == 10<\/pre>\n
Time Complexity:<\/strong> O(ElogE) or O(ElogV). Sorting of edges takes O(ELogE) time. After sorting, we iterate through all edges and apply find-union algorithm. The find and union operations can take atmost O(LogV) time. So overall complexity is O(ELogE + ELogV) time. The value of E can be atmost O(V2<\/sup>), so O(LogV) are O(LogE) same. Therefore, overall time complexity is O(ElogE) or O(ElogV)<\/p>\n[ad type=”banner”]\n","protected":false},"excerpt":{"rendered":"
(Kruskal\u2019s Minimum Spanning Tree Algorithm) – Minimum Spanning Tree A single graph can have many different spanning trees. A minimum spanning tree.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,76379],"tags":[70774,78372,70781,78371,78374,78373,70770,70804],"class_list":["post-26347","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-minimum-spanning-tree","tag-kruskals-algorithm-c","tag-kruskals-algorithm-geeksforgeeks","tag-kruskals-algorithm-in-c","tag-kruskals-algorithm-java","tag-kruskals-algorithm-pseudocode","tag-kruskals-algorithm-time-complexity","tag-prims-algorithm-example","tag-prims-algorithm-minimum-spanning-tree"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26347","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=26347"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26347\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26347"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26347"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26347"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}