Assignment 20
Name: Archit Bhandare Roll No: 66 Batch: F3
Title: Implementation of Kruskal's Algorithm for minimum spanning tree in
C
CODE:
#include <stdio.h>
#include <stdlib.h>
// Structure to represent an edge
struct Edge {
int src, dest, weight;
};
// Structure to represent a graph
struct Graph {
int V, E;
struct Edge* edges;
};
// Structure to represent a subset for union-find
struct Subset {
int parent;
int rank;
};
// Function to create a graph with V vertices and E edges
struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->E = E;
graph->edges = (struct Edge*)malloc(E * sizeof(struct Edge));
return graph;
}
// Function to find set of an element i (uses path compression)
int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
// Function to do union of two sets (uses union by rank)
void Union(struct Subset subsets[], int x, int y) {
int xroot = find(subsets, x);
int yroot = find(subsets, y);
if (subsets[xroot].rank < subsets[yroot].rank) {
subsets[xroot].parent = yroot;
} else if (subsets[xroot].rank > subsets[yroot].rank) {
subsets[yroot].parent = xroot;
} else {
subsets[yroot].parent = xroot;
subsets[xroot].rank++;
}
}
// Comparison function to sort edges by weight
int compareEdges(const void* a, const void* b) {
struct Edge* edgeA = (struct Edge*)a;
struct Edge* edgeB = (struct Edge*)b;
return edgeA->weight - edgeB->weight;
}
// Function to implement Kruskal's algorithm
void KruskalMST(struct Graph* graph) {
int V = graph->V;
struct Edge result[V]; // This will store the resulting MST
int e = 0; // Index variable for result[]
int i = 0; // Index variable for sorted edges
// Step 1: Sort all the edges in non-decreasing order of their weight
qsort(graph->edges, graph->E, sizeof(graph->edges[0]), compareEdges);
// Allocate memory for creating V subsets
struct Subset* subsets = (struct Subset*)malloc(V * sizeof(struct Subset));
// Create V subsets with single elements
for (int v = 0; v < V; v++) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
// Number of edges to be taken is equal to V-1
while (e < V - 1 && i < graph->E) {
// Step 2: Pick the smallest edge. Check if it forms a cycle
struct Edge nextEdge = graph->edges[i++];
int x = find(subsets, nextEdge.src);
int y = find(subsets, nextEdge.dest);
// If including this edge does not cause a cycle, include it in result
// and move to the next edge
if (x != y) {
result[e++] = nextEdge;
Union(subsets, x, y);
}
}
// Print the resulting MST
printf("Edges in the Minimum Spanning Tree:\n");
printf("Src - Dest : Weight\n");
for (i = 0; i < e; i++) {
printf("%d - %d : %d\n", result[i].src, result[i].dest, result[i].weight);
}
// Free allocated memory
free(subsets);
}
// Main function to test the Kruskal's algorithm
int main() {
int V = 4; // Number of vertices in graph
int E = 5; // Number of edges in graph
struct Graph* graph = createGraph(V, E);
// Add edges to the graph
graph->edges[0].src = 0;
graph->edges[0].dest = 1;
graph->edges[0].weight = 10;
graph->edges[1].src = 0;
graph->edges[1].dest = 2;
graph->edges[1].weight = 6;
graph->edges[2].src = 0;
graph->edges[2].dest = 3;
graph->edges[2].weight = 5;
graph->edges[3].src = 1;
graph->edges[3].dest = 3;
graph->edges[3].weight = 15;
graph->edges[4].src = 2;
graph->edges[4].dest = 3;
graph->edges[4].weight = 4;
// Function call
KruskalMST(graph);
// Free allocated memory for edges
free(graph->edges);
free(graph);
return 0;
}
OUTPUT:
