{"id":24968,"date":"2017-05-27T18:13:04","date_gmt":"2017-05-27T12:43:04","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=24968"},"modified":"2017-05-27T18:24:30","modified_gmt":"2017-05-27T12:54:30","slug":"kruskals-minimum-spanning-tree-algorithm","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/kruskals-minimum-spanning-tree-algorithm\/","title":{"rendered":"Kruskal\u2019s Minimum Spanning Tree Algorithm"},"content":{"rendered":"

What is Kruskals Minimum Spanning Tree Algorithm?<\/p>\n

Given a connected and undirected graph, a spanning tree<\/a> 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) 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?<\/p>\n

A 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?<\/p>\n

See this for applications of MST.<\/p>\n

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

Sort all the edges in non-decreasing order of their weight.\r\n\r\nPick 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\nRepeat step#2 until there are (V-1) edges in the spanning tree.<\/pre>\n[ad type=”banner”]\n
The step#2 uses Union-Find algorithm to detect cycle. So we recommend to read following post as a prerequisite.<\/p>\n
Union-Find Algorithm | Set 1 (Detect Cycle in a Graph)<\/p>\n
Union-Find Algorithm | Set 2 (Union By Rank and Path Compression)<\/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
Now pick all edges one by one from sorted list of edges<\/p>\n
1.<\/strong> Pick edge 7-6: No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
2.<\/strong> Pick edge 8-2: No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
3. Pick edge 6-5: No cycle is formed, include it.<\/strong><\/p>\n
\"Kruskal\u2019s<\/p>\n
4.<\/strong> Pick edge 0-1: No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
5.<\/strong> Pick edge 2-5: No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
6.<\/strong> Pick edge 8-6: Since including this edge results in cycle, discard it.<\/p>\n[ad type=”banner”]\n
7.<\/strong> Pick edge 2-3: No cycle is formed, include it.<\/p>\n
 <\/p>\n
\"Kruskal\u2019s<\/p>\n
8.<\/strong> Pick edge 7-8: Since including this edge results in cycle, discard it.<\/p>\n
9.<\/strong> Pick edge 0-7: No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
10.<\/strong> Pick edge 1-2: Since including this edge results in cycle, discard it.<\/p>\n
11.<\/strong> Pick edge 3-4: No cycle is formed, include it.<\/p>\n
\"Kruskal\u2019s<\/p>\n
Since the number of edges included equals (V \u2013 1), the algorithm stops here.<\/p>\n
\n
Recommended:<\/h4>\n
Please try your approach on {IDE}<\/u><\/b> first, before moving on to the solution.<\/h4>\n
C++<\/strong><\/h4>\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
[ad type=”banner”]<\/h4>\n
JAVA<\/strong><\/h4>\n<\/div>\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();    }}\/\/This code is contributed by Aakash Hasija<\/code><\/pre> <\/div>\n
Python<\/strong><\/h4>\n
 
 Python<\/span> <\/div> 
# Python program for Kruskal's algorithm to find Minimum Spanning Tree# of a given connected, undirected and weighted graph from collections import defaultdict #Class to represent a graphclass Graph:     def __init__(self,vertices):        self.V= vertices #No. of vertices        self.graph = [] # default dictionary to store graph               # function to add an edge to graph    def addEdge(self,u,v,w):        self.graph.append([u,v,w])     # A utility function to find set of an element i    # (uses path compression technique)    def find(self, parent, i):        if parent[i] == i:            return i        return self.find(parent, parent[i])     # A function that does union of two sets of x and y    # (uses union by rank)    def union(self, parent, rank, x, y):        xroot = self.find(parent, x)        yroot = self.find(parent, y)         # Attach smaller rank tree under root of high rank tree        # (Union by Rank)        if rank[xroot] < rank[yroot]:            parent[xroot] = yroot        elif rank[xroot] > rank[yroot]:            parent[yroot] = xroot        #If ranks are same, then make one as root and increment        # its rank by one        else :            parent[yroot] = xroot            rank[xroot] += 1     # The main function to construct MST using Kruskal's algorithm    def KruskalMST(self):         result =[] #This will store the resultant MST         i = 0 # An index variable, used for sorted edges        e = 0 # An index variable, used for result[]         #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 graph        self.graph =  sorted(self.graph,key=lambda item: item[2])        #print self.graph         parent = [] ; rank = []         # Create V subsets with single elements        for node in range(self.V):            parent.append(node)            rank.append(0)             # Number of edges to be taken is equal to V-1        while e < self.V -1 :             # Step 2: Pick the smallest edge and increment the index            # for next iteration            u,v,w =  self.graph[i]            i = i + 1            x = self.find(parent, u)            y = self.find(parent ,v)             # If including this edge does't cause cycle, include it            # in result and increment the index of result for next edge            if x != y:                e = e + 1                  result.append([u,v,w])                self.union(parent, rank, x, y)                      # Else discard the edge         # print the contents of result[] to display the built MST        print "Following are the edges in the constructed MST"        for u,v,weight  in result:            #print str(u) + " -- " + str(v) + " == " + str(weight)            print ("%d -- %d == %d" % (u,v,weight))  g = Graph(4)g.addEdge(0, 1, 10)g.addEdge(0, 2, 6)g.addEdge(0, 3, 5)g.addEdge(1, 3, 15)g.addEdge(2, 3, 4) g.KruskalMST() #This code is contributed by Neelam Yadav<\/code><\/pre> <\/div>\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","protected":false},"excerpt":{"rendered":"
Kruskal\u2019s Minimum Spanning Tree Algorithm-Greedy Algorithm-Given a connected and undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees<\/p>\n","protected":false},"author":1,"featured_media":25352,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70144],"tags":[70802,70807,70598,70796,70799,70764,70769,70783,70784,70754,70774,70794,70781,70772,70806,70805,70767,70793,70795,70779,70766,70792,70763,70770,70775,70785,70804,70778,70776,70801,70777,70786,70773,70046,70765,70791,70797,70798,70771,70803,70788,70782],"class_list":["post-24968","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-greedy-algorithm","tag-complexity-of-kruskal-algorithm","tag-complexity-of-prims-algorithm","tag-graph-algorithms","tag-kruskal","tag-kruskal-algo","tag-kruskal-algorithm","tag-kruskal-algorithm-example","tag-kruskal-algorithm-in-c","tag-kruskal-program-in-c","tag-kruskals-algorithm","tag-kruskals-algorithm-c","tag-kruskals-algorithm-example","tag-kruskals-algorithm-in-c","tag-kruskals-algorithm-minimum-spanning-tree","tag-maximum-spanning-tree","tag-minimum-cost-spanning-tree","tag-minimum-spanning-tree","tag-minimum-spanning-tree-algorithm","tag-minimum-spanning-tree-example","tag-minimum-spanning-tree-prims-algorithm","tag-prim","tag-prim-algorithm","tag-prims-algorithm","tag-prims-algorithm-example","tag-prims-algorithm-for-minimum-spanning-tree","tag-prims-algorithm-in-c","tag-prims-algorithm-minimum-spanning-tree","tag-prims-algorithm-pseudocode","tag-prims-algorithm-with-example","tag-prims-and-kruskal-algorithm","tag-prims-and-kruskal-algorithm-with-example","tag-prims-program-in-c","tag-prism-algorithm","tag-quicksort","tag-spanning-tree","tag-spanning-tree-algorithm","tag-spanning-tree-example","tag-spanning-tree-in-data-structure","tag-time-complexity-of-kruskal-algorithm","tag-tree-algorithms","tag-what-is-span","tag-what-is-spanning-tree"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24968","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=24968"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/24968\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/25352"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=24968"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=24968"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=24968"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}