Kruskal's algorithm
Published by: Anil K. Panta
Kruskal’s Algorithm | Minimum Spanning Tree
In graph theory, the Minimum Spanning Tree (MST) is a tree that connects all vertices with the minimum possible total edge weight and no cycles. One of the most popular algorithms to find an MST is Kruskal’s Algorithm.
What is Kruskal’s Algorithm?
Kruskal’s Algorithm is a greedy algorithm that builds the MST by:
Sorting all the edges of the graph in non-decreasing order of weight.
Adding the smallest edge to the MST that doesn't form a cycle.
Repeating the process until there are exactly (V - 1) edges in the MST.
It uses a Disjoint Set (Union-Find) data structure to detect cycles efficiently.
Steps to Find MST using Kruskal's Algorithm:
Sort all the edges by increasing weight.
Initialize a parent array for each node (Disjoint Set).
Traverse each edge:
If adding it doesn't create a cycle, include it in the MST.
Otherwise, skip it.
Stop when the MST has (V – 1) edges.
Key Terms:
Greedy Algorithm: Always picks the locally optimal solution at each step.
Disjoint Set (Union-Find): A structure to keep track of connected components.
Cycle Detection: Avoid adding edges that connect nodes already in the same set.
Kruskal’s Algorithm in C
Here’s a full C program demonstrating Kruskal's Algorithm:
#include <stdio.h>
#include <stdlib.h>
#define EDGE_COUNT 5 // Number of edges
// Comparator to sort edges by weight
int comparator(const int a[], const int b[]) {
return a[2] - b[2];
}
// Initialize parent and rank arrays
void makeSet(int parent[], int rank[], int n) {
for (int i = 0; i < n; i++) {
parent[i] = i;
rank[i] = 0;
}
}
// Find the representative (parent) of a node
int findParent(int parent[], int u) {
if (parent[u] != u)
parent[u] = findParent(parent, parent[u]); // Path compression
return parent[u];
}
// Union of two sets
void unionSet(int u, int v, int parent[], int rank[]) {
u = findParent(parent, u);
v = findParent(parent, v);
if (rank[u] < rank[v]) {
parent[u] = v;
} else if (rank[u] > rank[v]) {
parent[v] = u;
} else {
parent[v] = u;
rank[u]++;
}
}
// Kruskal's Algorithm
int kruskalAlgo(int n, int edges[EDGE_COUNT][3]) {
// Sort edges by weight
qsort(edges, EDGE_COUNT, sizeof(edges[0]), (int(*)(const void*, const void*))comparator);
int parent[n];
int rank[n];
makeSet(parent, rank, n);
int minCost = 0;
printf("Edges in the MST:\n");
int edgeCount = 0;
for (int i = 0; i < EDGE_COUNT && edgeCount < n - 1; i++) {
int u = edges[i][0];
int v = edges[i][1];
int wt = edges[i][2];
int parentU = findParent(parent, u);
int parentV = findParent(parent, v);
if (parentU != parentV) {
unionSet(u, v, parent, rank);
printf("%d -- %d == %d\n", u, v, wt);
minCost += wt;
edgeCount++;
}
}
return minCost;
}
int main() {
int V = 4;
int edges[EDGE_COUNT][3] = {
{0, 1, 10},
{0, 2, 6},
{0, 3, 5},
{1, 3, 15},
{2, 3, 4}
};
int cost = kruskalAlgo(V, edges);
printf("Minimum Cost of Spanning Tree: %d\n", cost);
return 0;
}
Output:
Edges in the MST:
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimum Cost of Spanning Tree: 19
Time & Space Complexity
Where:
E = Number of edges
V = Number of vertices
Real-World Applications of Kruskal’s Algorithm:
Network Design (LAN/WAN wiring, telephone lines)
Road or Rail Planning
Minimum Cost Routing
Approximation Algorithms in TSP
Summary
Final Thought:
Kruskal’s Algorithm is one of the most efficient and intuitive methods to find the minimum spanning tree, especially useful when the graph has fewer edges.
