Understanding Kruskal’s Algorithm
Kruskal’s algorithm is a greedy algorithm that finds the minimum spanning tree for a connected, weighted graph. The steps involved are:
- Sort All Edges: Begin by sorting all the edges in non-decreasing order of their weights.
- Initialize a Forest: Start with an empty forest, which will grow into the minimum spanning tree.
- Add Edges: For each edge in the sorted list, add it to the forest if it doesn’t create a cycle. This is typically checked using a Union-Find data structure.
- Repeat Until MST is Complete: Continue adding edges until there are V−1V – 1V−1 edges in the tree (where VVV is the number of vertices).
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
// Structure to represent an edge
struct Edge {
int src, dest, weight;
};
// Structure to represent a subset for union-find
struct Subset {
int parent;
int rank;
};
// Function to compare two edges (for qsort)
int compare(const void* a, const void* b) {
struct Edge* edge1 = (struct Edge*)a;
struct Edge* edge2 = (struct Edge*)b;
return edge1->weight - edge2->weight;
}
// Find function for union-find
int find(struct Subset subsets[], int i) {
if (subsets[i].parent != i) {
subsets[i].parent = find(subsets, subsets[i].parent);
}
return subsets[i].parent;
}
// Union function for union-find
void unionSubsets(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++;
}
}
// Function to implement Kruskal's algorithm
void kruskal(struct Edge edges[], int V, int E) {
struct Edge result[MAX]; // To store the resulting MST
struct Subset subsets[MAX];
// Step 1: Sort all edges
qsort(edges, E, sizeof(edges[0]), compare);
// Create V subsets with single elements
for (int v = 0; v < V; ++v) {
subsets[v].parent = v;
subsets[v].rank = 0;
}
int e = 0; // Index variable for result
int i = 0; // Index variable for sorted edges
while (e < V - 1 && i < E) {
// Step 2: Pick the smallest edge
struct Edge nextEdge = edges[i++];
// Find the subsets of the vertices of the edge
int x = find(subsets, nextEdge.src);
int y = find(subsets, nextEdge.dest);
// If they are in different subsets, include this edge in the result
if (x != y) {
result[e++] = nextEdge;
unionSubsets(subsets, x, y);
}
}
// Print the resulting MST
printf("Edges in the Minimum Spanning Tree (Kruskal's Algorithm):\n");
for (i = 0; i < e; ++i) {
printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
}
}
// Main function
int main() {
int V, E;
printf("Enter number of vertices: ");
scanf("%d", &V);
printf("Enter number of edges: ");
scanf("%d", &E);
struct Edge edges[E];
printf("Enter edges (src dest weight): \n");
for (int i = 0; i < E; i++) {
scanf("%d %d %d", &edges[i].src, &edges[i].dest, &edges[i].weight);
}
kruskal(edges, V, E);
return 0;
}
Explanation of Kruskal’s Code
- Edge Structure: Each edge has a source, destination, and weight.
- Union-Find: We use a
Subsetstructure to manage disjoint sets. Thefindfunction retrieves the set of an element, while theunionSubsetsfunction merges two sets. - Sorting: We sort the edges by weight using
qsort. - Building the MST: We iterate through the sorted edges and add them to the MST if they connect disjoint sets.
- Output: Finally, we print the edges included in the MST.
Sample Input and Output for Kruskal’s Algorithm
Input:
mathematicaCopy codeEnter number of vertices: 4
Enter number of edges: 5
Enter edges (src dest weight):
0 1 10
0 2 6
0 3 5
1 3 15
2 3 4
Output:
mathematicaCopy codeEdges in the Minimum Spanning Tree (Kruskal's Algorithm):
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
