# C Program to Find Minimum Spanning Tree using Kruskal’s Algorithm

«
»
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.
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.

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

Output:

```\$ gcc KruskalsMST.c
\$ ./a.out

Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10```

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube 