{"id":26302,"date":"2017-10-26T21:02:24","date_gmt":"2017-10-26T15:32:24","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26302"},"modified":"2017-10-26T21:02:24","modified_gmt":"2017-10-26T15:32:24","slug":"minimum-spanning-tree","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/minimum-spanning-tree\/","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 for applications of MST.<\/p>\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 to detect cycle. So we recommend to read following post as a prerequisite.
\nUnion-Find Algorithm | Set 1 (Detect Cycle in a Graph)
\nUnion-Find Algorithm | Set 2 (Union By Rank and Path Compression)<\/p>\n[ad type=”banner”]\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
 <\/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
 <\/p>\n
 <\/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
C++ Programming<\/p>\n
 
 <\/div> 
\/\/ C++ program for Kruskal's algorithm to find Minimum Spanning Tree\/\/ of a given connected, undirected and weighted graph#include <stdio.h>#include <stdlib.h>#include <string.h> \/\/ a structure to represent a weighted edge in graphstruct Edge{    int src, dest, weight;}; \/\/ a structure to represent a connected, undirected and weighted graphstruct Graph{    \/\/ V-> Number of vertices, E-> Number of edges    int V, E;     \/\/ graph is represented as an array of edges. Since the graph is    \/\/ undirected, the edge from src to dest is also edge from dest    \/\/ to src. Both are counted as 1 edge here.    struct Edge* edge;}; \/\/ Creates a graph with V vertices and E edgesstruct Graph* createGraph(int V, int E){    struct Graph* graph = (struct Graph*) malloc( sizeof(struct Graph) );    graph->V = V;    graph->E = E;     graph->edge = (struct Edge*) malloc( graph->E * sizeof( struct Edge ) );     return graph;} \/\/ A structure to represent a subset for union-findstruct subset{    int parent;    int rank;}; \/\/ A utility function to find set of an element i\/\/ (uses path compression technique)int find(struct 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(struct 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++;    }} \/\/ Compare two edges according to their weights.\/\/ Used in qsort() for sorting an array of edgesint myComp(const void* a, const void* b){    struct Edge* a1 = (struct Edge*)a;    struct Edge* b1 = (struct Edge*)b;    return a1->weight > b1->weight;} \/\/ The main function to construct MST using Kruskal's algorithmvoid KruskalMST(struct Graph* graph){    int V = graph->V;    struct Edge result[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     \/\/ 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    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);     \/\/ Allocate memory for creating V ssubsets    struct subset *subsets =        (struct subset*) malloc( V * sizeof(struct subset) );     \/\/ Create V subsets with single elements    for (int v = 0; v < V; ++v)    {        subsets[v].parent = v;        subsets[v].rank = 0;    }     \/\/ 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        struct Edge next_edge = graph->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    printf("Following are the edges in the constructed MST\\n");    for (i = 0; i < e; ++i)        printf("%d -- %d == %d\\n", result[i].src, result[i].dest,                                                   result[i].weight);    return;} \/\/ Driver program to test above functionsint main(){    \/* 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    struct Graph* graph = createGraph(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;     KruskalMST(graph);     return 0;}<\/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 (MST).<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[69969,83620,76379],"tags":[70774,78372,70781,78371,78374,78373,70770,70804],"class_list":["post-26302","post","type-post","status-publish","format-standard","hentry","category-algorithm","category-kruskals-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\/26302","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=26302"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26302\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26302"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26302"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26302"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}