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