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