C++ Program to Apply the Kruskal’s Algorithm to Find the Minimum Spanning Tree of a Graph

«
»
This is a C++ Program to find the minimum spanning tree of the given graph. Kruskal’s algorithm is a greedy algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).

Here is source code of the C++ Program to Apply the Kruskal’s Algorithm to Find the Minimum Spanning Tree of a Graph. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <iostream>
  5.  
  6. using namespace std;
  7.  
  8. // a structure to represent a weighted edge in graph
  9. struct Edge
  10. {
  11.     int src, dest, weight;
  12. };
  13.  
  14. // a structure to represent a connected, undirected and weighted graph
  15. struct Graph
  16. {
  17.         // V-> Number of vertices, E-> Number of edges
  18.         int V, E;
  19.  
  20.         // graph is represented as an array of edges. Since the graph is
  21.         // undirected, the edge from src to dest is also edge from dest
  22.         // to src. Both are counted as 1 edge here.
  23.         struct Edge* edge;
  24. };
  25.  
  26. // Creates a graph with V vertices and E edges
  27. struct Graph* createGraph(int V, int E)
  28. {
  29.     struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
  30.     graph->V = V;
  31.     graph->E = E;
  32.  
  33.     graph->edge = (struct Edge*) malloc(graph->E * sizeof(struct Edge));
  34.  
  35.     return graph;
  36. }
  37.  
  38. // A structure to represent a subset for union-find
  39. struct subset
  40. {
  41.         int parent;
  42.         int rank;
  43. };
  44.  
  45. // A utility function to find set of an element i
  46. // (uses path compression technique)
  47. int find(struct subset subsets[], int i)
  48. {
  49.     // find root and make root as parent of i (path compression)
  50.     if (subsets[i].parent != i)
  51.         subsets[i].parent = find(subsets, subsets[i].parent);
  52.  
  53.     return subsets[i].parent;
  54. }
  55.  
  56. // A function that does union of two sets of x and y
  57. // (uses union by rank)
  58. void Union(struct subset subsets[], int x, int y)
  59. {
  60.     int xroot = find(subsets, x);
  61.     int yroot = find(subsets, y);
  62.  
  63.     // Attach smaller rank tree under root of high rank tree
  64.     // (Union by Rank)
  65.     if (subsets[xroot].rank < subsets[yroot].rank)
  66.         subsets[xroot].parent = yroot;
  67.     else if (subsets[xroot].rank > subsets[yroot].rank)
  68.         subsets[yroot].parent = xroot;
  69.  
  70.     // If ranks are same, then make one as root and increment
  71.     // its rank by one
  72.     else
  73.     {
  74.         subsets[yroot].parent = xroot;
  75.         subsets[xroot].rank++;
  76.     }
  77. }
  78.  
  79. // Compare two edges according to their weights.
  80. // Used in qsort() for sorting an array of edges
  81. int myComp(const void* a, const void* b)
  82. {
  83.     struct Edge* a1 = (struct Edge*) a;
  84.     struct Edge* b1 = (struct Edge*) b;
  85.     return a1->weight > b1->weight;
  86. }
  87.  
  88. // The main function to construct MST using Kruskal's algorithm
  89. void KruskalMST(struct Graph* graph)
  90. {
  91.     int V = graph->V;
  92.     struct Edge result[V]; // Tnis will store the resultant MST
  93.     int e = 0; // An index variable, used for result[]
  94.     int i = 0; // An index variable, used for sorted edges
  95.  
  96.     // Step 1:  Sort all the edges in non-decreasing order of their weight
  97.     // If we are not allowed to change the given graph, we can create a copy of
  98.     // array of edges
  99.     qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
  100.  
  101.     // Allocate memory for creating V ssubsets
  102.     struct subset *subsets = (struct subset*) malloc(V * sizeof(struct subset));
  103.  
  104.     // Create V subsets with single elements
  105.     for (int v = 0; v < V; ++v)
  106.     {
  107.         subsets[v].parent = v;
  108.         subsets[v].rank = 0;
  109.     }
  110.  
  111.     // Number of edges to be taken is equal to V-1
  112.     while (e < V - 1)
  113.     {
  114.         // Step 2: Pick the smallest edge. And increment the index
  115.         // for next iteration
  116.         struct Edge next_edge = graph->edge[i++];
  117.  
  118.         int x = find(subsets, next_edge.src);
  119.         int y = find(subsets, next_edge.dest);
  120.  
  121.         // If including this edge does't cause cycle, include it
  122.         // in result and increment the index of result for next edge
  123.         if (x != y)
  124.         {
  125.             result[e++] = next_edge;
  126.             Union(subsets, x, y);
  127.         }
  128.         // Else discard the next_edge
  129.     }
  130.  
  131.     // print the contents of result[] to display the built MST
  132.     cout<<"Following are the edges in the constructed MST\n";
  133.     for (i = 0; i < e; ++i)
  134.         printf("%d -- %d == %d\n", result[i].src, result[i].dest,
  135.                 result[i].weight);
  136.     return;
  137. }
  138.  
  139. // Driver program to test above functions
  140. int main()
  141. {
  142.     /* Let us create following weighted graph
  143.          10
  144.      0--------1
  145.      | \      |
  146.     6|   \5   |15
  147.      |      \ |
  148.      2--------3
  149.      4       */
  150.     int V = 4; // Number of vertices in graph
  151.     int E = 5; // Number of edges in graph
  152.     struct Graph* graph = createGraph(V, E);
  153.  
  154.     // add edge 0-1
  155.     graph->edge[0].src = 0;
  156.     graph->edge[0].dest = 1;
  157.     graph->edge[0].weight = 10;
  158.  
  159.     // add edge 0-2
  160.     graph->edge[1].src = 0;
  161.     graph->edge[1].dest = 2;
  162.     graph->edge[1].weight = 6;
  163.  
  164.     // add edge 0-3
  165.     graph->edge[2].src = 0;
  166.     graph->edge[2].dest = 3;
  167.     graph->edge[2].weight = 5;
  168.  
  169.     // add edge 1-3
  170.     graph->edge[3].src = 1;
  171.     graph->edge[3].dest = 3;
  172.     graph->edge[3].weight = 15;
  173.  
  174.     // add edge 2-3
  175.     graph->edge[4].src = 2;
  176.     graph->edge[4].dest = 3;
  177.     graph->edge[4].weight = 4;
  178.  
  179.     KruskalMST(graph);
  180.  
  181.     return 0;
  182. }

Output:

advertisement
$ g++ KruskalsMST.cpp
$ a.out
 
Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.