# 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:

```\$ 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)

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

Note: Join free Sanfoundry classes at Telegram or Youtube