Kruskal's Algorithm
Last updated
Kruskal's algorithm builds a minimum spanning tree (MST) - the cheapest set of edges that connects every node with no cycles. It sorts all edges by weight, then greedily adds the next-cheapest edge as long as it joins two nodes that are not already connected. Press play above to watch the tree grow, one cheapest safe edge at a time.
The "already connected?" check is done with a union-find (disjoint-set) data structure: each edge is skipped if its two endpoints are already in the same component, because adding it would form a cycle. Sorting dominates the cost, giving O(E log E) overall. Kruskal shines on sparse graphs.
Time & space complexity
| Measure | Complexity | Notes |
|---|---|---|
| Time | O(E log E) | Dominated by sorting the edges |
| Union-find ops | ≈ O(E α(V)) | Near-constant per check with path compression |
| Space | O(V + E) | Edge list + disjoint-set structure |
| Best for | Sparse graphs | Works from a global edge list |
Step by step
| Step | What happens |
|---|---|
| 1 | Sort every edge by weight, ascending. |
| 2 | Put each node in its own component (union-find). |
| 3 | Take the next-cheapest edge. |
| 4 | If its endpoints are in different components, add it to the tree and union them. |
| 5 | Otherwise skip it (it would create a cycle). |
| 6 | Stop once the tree has V − 1 edges. |
Worked example
Graph with nodes A, B, C, D and edges A-B(1), B-C(2), A-C(3), C-D(4), B-D(5). Sorted edges: A-B(1), B-C(2), A-C(3), C-D(4), B-D(5):
| Edge (weight) | Components before | Action |
|---|---|---|
A-B(1) | {A} {B} {C} {D} | Different components - add to MST, union to {A,B}. |
B-C(2) | {A,B} {C} {D} | Different components - add to MST, union to {A,B,C}. |
A-C(3) | {A,B,C} {D} | A and C already together - skip (would form a cycle). |
C-D(4) | {A,B,C} {D} | Different components - add to MST, union to {A,B,C,D}. |
| Stop | {A,B,C,D} | Tree has V - 1 = 3 edges. MST = A-B, B-C, C-D, total weight 7. |
When to use Kruskal's algorithm
| Use it when | Avoid it when |
|---|---|
| The graph is sparse (few edges relative to nodes). | The graph is dense - Prim's with a heap is usually faster. |
| Edges are already available as a global list you can sort. | Edges arrive only through adjacency lists you must scan per node. |
| You want a simple implementation backed by union-find. | You need the tree to grow from one specific start node. |
| You want to build a spanning forest of a disconnected graph. | You must handle edges streaming in without a full sort. |
Kruskal's Algorithm code
A clean, runnable Kruskal's Algorithm implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Kruskal's Algorithm code in Python
Python
1def find(parent, x):2 while parent[x] != x:3 parent[x] = parent[parent[x]] # path compression4 x = parent[x]5 return x6
7
8def kruskal(vertices, edges):9 # Take the cheapest edge that does not close a cycle10 parent = {v: v for v in vertices}11 mst, total = [], 012 for w, u, v in sorted(edges):13 root_u, root_v = find(parent, u), find(parent, v)14 if root_u != root_v:15 parent[root_u] = root_v16 mst.append((u, v, w))17 total += w18 return mst, total19
20
21vertices = ["A", "B", "C", "D", "E"]22edges = [23 (4, "A", "B"), (1, "A", "C"), (3, "B", "C"), (2, "B", "D"),24 (5, "C", "D"), (6, "C", "E"), (7, "D", "E"),25]26
27mst, total = kruskal(vertices, edges)28for u, v, w in mst:29 print(f"{u} - {v} (weight {w})")30print("Total MST weight:", total)Kruskal's Algorithm code in JavaScript
JavaScript
1const nodes = ["A", "B", "C", "D", "E"];2const edges = [3 ["A", "B", 4], ["A", "C", 2], ["B", "C", 1], ["B", "D", 5],4 ["C", "D", 8], ["C", "E", 10], ["D", "E", 2],5];6
7function kruskal() {8 // Union-find with path compression detects cycles cheaply9 const parent = Object.fromEntries(nodes.map((n) => [n, n]));10 const find = (x) => (parent[x] === x ? x : (parent[x] = find(parent[x])));11 const mst = [];12 let total = 0;13 const sorted = [...edges].sort((a, b) => a[2] - b[2]);14 for (const [u, v, w] of sorted) {15 const rootU = find(u);16 const rootV = find(v);17 if (rootU !== rootV) {18 parent[rootU] = rootV;19 mst.push(`${u}-${v} (${w})`);20 total += w;21 }22 }23 return { mst, total };24}25
26const { mst, total } = kruskal();27console.log("MST edges:", mst.join(", "));28console.log("Total weight:", total);Kruskal's Algorithm code in Java
Java
1import java.util.Arrays;2
3public class Main {4 static int[] parent;5
6 static int find(int x) {7 if (parent[x] != x) parent[x] = find(parent[x]); // path compression8 return parent[x];9 }10
11 static boolean union(int a, int b) {12 int rootA = find(a), rootB = find(b);13 if (rootA == rootB) return false; // would create a cycle14 parent[rootA] = rootB;15 return true;16 }17
18 public static void main(String[] args) {19 int n = 6;20 int[][] edges = {21 {0, 1, 4}, {0, 2, 3}, {1, 2, 1}, {1, 3, 2},22 {2, 3, 4}, {3, 4, 2}, {4, 5, 6}, {2, 5, 7}23 };24 Arrays.sort(edges, (a, b) -> a[2] - b[2]);25 parent = new int[n];26 for (int i = 0; i < n; i++) parent[i] = i;27
28 int total = 0, used = 0;29 for (int[] e : edges) {30 if (union(e[0], e[1])) {31 System.out.println("Take edge " + e[0] + "-" + e[1] + " (weight " + e[2] + ")");32 total += e[2];33 if (++used == n - 1) break;34 }35 }36 System.out.println("MST total weight: " + total);37 }38}Kruskal's Algorithm code in C++
C++
1#include <algorithm>2#include <iostream>3#include <numeric>4#include <vector>5
6struct Edge {7 int u, v, weight;8};9
10struct DSU {11 std::vector<int> parent;12 explicit DSU(int n) : parent(n) {13 std::iota(parent.begin(), parent.end(), 0);14 }15 int find(int x) {16 if (parent[x] != x) parent[x] = find(parent[x]); // path compression17 return parent[x];18 }19 bool unite(int a, int b) {20 int ra = find(a), rb = find(b);21 if (ra == rb) return false; // would create a cycle22 parent[ra] = rb;23 return true;24 }25};26
27int main() {28 const int n = 5;29 std::vector<Edge> edges = {30 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},31 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},32 };33 // Greedily take the cheapest edge that connects two components34 std::sort(edges.begin(), edges.end(),35 [](const Edge& a, const Edge& b) { return a.weight < b.weight; });36 DSU dsu(n);37 int total = 0;38 std::cout << "MST edges:\n";39 for (const Edge& e : edges) {40 if (dsu.unite(e.u, e.v)) {41 std::cout << " " << e.u << " - " << e.v42 << " (weight " << e.weight << ")\n";43 total += e.weight;44 }45 }46 std::cout << "Total weight: " << total << "\n";47 return 0;48}Kruskal's Algorithm code in C
C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5#define N 56
7typedef struct {8 int u, v, weight;9} Edge;10
11int parent[N];12
13int find(int x) {14 if (parent[x] != x) parent[x] = find(parent[x]); // path compression15 return parent[x];16}17
18bool unite(int a, int b) {19 int ra = find(a), rb = find(b);20 if (ra == rb) return false; // would create a cycle21 parent[ra] = rb;22 return true;23}24
25int cmpEdge(const void* a, const void* b) {26 return ((const Edge*)a)->weight - ((const Edge*)b)->weight;27}28
29int main(void) {30 Edge edges[] = {31 {0, 1, 4}, {0, 2, 2}, {1, 2, 1}, {1, 3, 5},32 {2, 3, 8}, {2, 4, 10}, {3, 4, 3},33 };34 int m = sizeof(edges) / sizeof(edges[0]);35 for (int i = 0; i < N; i++) parent[i] = i;36 // Greedily take the cheapest edge that connects two components37 qsort(edges, m, sizeof(Edge), cmpEdge);38 int total = 0;39 printf("MST edges:\n");40 for (int i = 0; i < m; i++) {41 if (unite(edges[i].u, edges[i].v)) {42 printf(" %d - %d (weight %d)\n",43 edges[i].u, edges[i].v, edges[i].weight);44 total += edges[i].weight;45 }46 }47 printf("Total weight: %d\n", total);48 return 0;49}Kruskal's Algorithm FAQ
What is a minimum spanning tree?
A minimum spanning tree (MST) of a connected weighted graph is a subset of edges that connects all the nodes with no cycles and the smallest possible total weight. It has exactly
V - 1 edges for V nodes.What is the difference between Kruskal's and Prim's algorithm?
Both build a minimum spanning tree greedily. Kruskal sorts all edges globally and adds the cheapest one that doesn't form a cycle, using union-find. Prim grows a single tree outward from a start node, always adding the cheapest edge that leaves the tree. Kruskal suits sparse graphs; Prim (with a heap) suits dense ones.
Why does Kruskal's algorithm use union-find?
Before adding an edge, Kruskal must check whether its two endpoints are already connected - adding such an edge would create a cycle. Union-find (disjoint-set) answers "are these in the same component?" and merges components in near-constant amortized time, which keeps the algorithm efficient.
When should I use Kruskal's algorithm instead of Prim's?
Prefer Kruskal when the graph is sparse and you already have all edges as a list you can sort - the
O(E log E) sort is cheap when E is small. Prim's algorithm with a binary or Fibonacci heap tends to win on dense graphs where E approaches V², because it avoids sorting every edge up front.Does Kruskal's algorithm work on disconnected graphs?
Yes. If the graph is disconnected, Kruskal simply cannot reach
V - 1 edges and instead produces a minimum spanning forest - one MST per connected component. This falls out naturally because union-find never merges nodes that have no path between them.What is the most common mistake when implementing Kruskal's algorithm?
Skipping the union-find's path compression and union by rank, which drops each connectivity check from near-constant to nearly linear and can dominate the runtime. Another frequent bug is forgetting to actually union the two components after adding an edge, which lets later edges create cycles.
Related resources
More visualizations
