Kruskal's Algorithm
Graph Selection
Playback Controls
Select a graph to begin MST visualization
Kruskal's Info
Key Features:
- • Finds Minimum Spanning Tree
- • Uses greedy approach
- • Time complexity: O(E log E)
- • Uses Union-Find data structure
- • Avoids cycles in the tree
Legend:
Current Edge
MST Edges
Connected Components
Reference implementation of Kruskal's Algorithm. Select a language tab to view and copy the code.
#include <stdlib.h>
#define MAX 100
typedef struct { int u, v, w; } Edge;
int parent[MAX], rank_[MAX];
int find(int x) {
if (parent[x] != x) parent[x] = find(parent[x]); // path compression
return parent[x];
}
void unite(int x, int y) {
int px = find(x), py = find(y);
if (rank_[px] < rank_[py]) parent[px] = py;
else if (rank_[px] > rank_[py]) parent[py] = px;
else { parent[py] = px; rank_[px]++; }
}
int cmp(const void* a, const void* b) { return ((Edge*)a)->w - ((Edge*)b)->w; }
int kruskal(Edge edges[], int num_e, int n) {
for (int i = 0; i < n; i++) { parent[i] = i; rank_[i] = 0; }
qsort(edges, num_e, sizeof(Edge), cmp);
int mst_weight = 0;
for (int i = 0; i < num_e; i++) {
if (find(edges[i].u) != find(edges[i].v)) {
unite(edges[i].u, edges[i].v);
mst_weight += edges[i].w;
}
}
return mst_weight;
}#include <vector>
#include <algorithm>
struct Edge { int u, v, w; };
struct DSU {
std::vector<int> parent, rank_;
DSU(int n) : parent(n), rank_(n, 0) {
std::iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
return parent[x] == x ? x : parent[x] = find(parent[x]);
}
bool unite(int x, int y) {
x = find(x); y = find(y);
if (x == y) return false;
if (rank_[x] < rank_[y]) std::swap(x, y);
parent[y] = x;
if (rank_[x] == rank_[y]) rank_[x]++;
return true;
}
};
int kruskal(int n, std::vector<Edge>& edges) {
std::sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b){ return a.w < b.w; });
DSU dsu(n);
int mst_weight = 0;
for (const auto& e : edges)
if (dsu.unite(e.u, e.v)) mst_weight += e.w;
return mst_weight;
}import java.util.*;
public static int kruskal(int n, int[][] edges) {
// Sort edges by weight
Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
int[] parent = new int[n], rank = new int[n];
for (int i = 0; i < n; i++) parent[i] = i;
int mstWeight = 0;
for (int[] e : edges) {
int pu = find(parent, e[0]), pv = find(parent, e[1]);
if (pu != pv) {
union(parent, rank, pu, pv);
mstWeight += e[2];
}
}
return mstWeight;
}
private static int find(int[] parent, int x) {
return parent[x] == x ? x : (parent[x] = find(parent, parent[x]));
}
private static void union(int[] parent, int[] rank, int x, int y) {
if (rank[x] < rank[y]) parent[x] = y;
else if (rank[x] > rank[y]) parent[y] = x;
else { parent[y] = x; rank[x]++; }
}def kruskal(n: int, edges: list[tuple[int,int,int]]) -> int:
parent = list(range(n))
rank = [0] * n
def find(x: int) -> int:
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]
def union(x: int, y: int) -> bool:
px, py = find(x), find(y)
if px == py: return False
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
edges.sort(key=lambda e: e[2])
mst_weight = 0
for u, v, w in edges:
if union(u, v):
mst_weight += w
return mst_weightfunction kruskal(n, edges) {
const parent = Array.from({length: n}, (_, i) => i);
const rank = new Array(n).fill(0);
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
function union(x, y) {
x = find(x); y = find(y);
if (x === y) return false;
if (rank[x] < rank[y]) [x, y] = [y, x];
parent[y] = x;
if (rank[x] === rank[y]) rank[x]++;
return true;
}
edges.sort((a, b) => a[2] - b[2]);
let mstWeight = 0;
for (const [u, v, w] of edges)
if (union(u, v)) mstWeight += w;
return mstWeight;
}Python — Code Walkthrough
Nested functions share closure over parent/rank
def find(x) ... def union(x, y) ...Python nested functions capture parent and rank from the enclosing scope by reference (closure). This avoids passing them as parameters on every call, keeping the signatures clean.
list(range(n)) initialises parent[i] = i
parent = list(range(n))range(n) generates 0, 1, …, n−1. Converting to list creates an editable copy. This is the most Pythonic way to initialise the Union-Find parent array.
Sort by third element of each tuple
edges.sort(key=lambda e: e[2])key=lambda e: e[2] extracts the weight from each (u, v, weight) edge tuple. sort is in-place, stable, and uses Timsort — O(E log E).
union returns bool — used in if
if union(u, v): mst_weight += wunion returns True only when u and v were in different components. Returning False for same-component merges keeps the main loop free of an explicit find-comparison.