Kruskal's Algorithm
Minimum Spanning Tree algorithm using greedy approach and Union-Find data structure. Sorts edges by weight and selects minimum weight edges that don't create cycles. Named after Joseph Kruskal, it's one of the most efficient MST algorithms for sparse graphs.
Visualization
Interactive visualization for Kruskal's Algorithm
Kruskal's MST Algorithm
Interactive visualization with step-by-step execution
Implementation
1class UnionFind {
2 parent: number[];
3 rank: number[];
4
5 constructor(n: number) {
6 this.parent = Array.from({length: n}, (_, i) => i);
7 this.rank = new Array(n).fill(0);
8 }
9
10 find(x: number): number {
11 if (this.parent[x] !== x) {
12 this.parent[x] = this.find(this.parent[x]);
13 }
14 return this.parent[x];
15 }
16
17 union(x: number, y: number): boolean {
18 const px = this.find(x);
19 const py = this.find(y);
20
21 if (px === py) return false;
22
23 if (this.rank[px] < this.rank[py]) {
24 this.parent[px] = py;
25 } else if (this.rank[px] > this.rank[py]) {
26 this.parent[py] = px;
27 } else {
28 this.parent[py] = px;
29 this.rank[px]++;
30 }
31
32 return true;
33 }
34}
35
36function kruskal(n: number, edges: [number, number, number][]): [number, number, number][] {
37 edges.sort((a, b) => a[2] - b[2]);
38 const uf = new UnionFind(n);
39 const mst: [number, number, number][] = [];
40
41 for (const [u, v, weight] of edges) {
42 if (uf.union(u, v)) {
43 mst.push([u, v, weight]);
44 if (mst.length === n - 1) break;
45 }
46 }
47
48 return mst;
49}Deep Dive
Theoretical Foundation
Kruskal's algorithm builds MST by sorting all edges by weight and greedily selecting minimum weight edges that don't create cycles. Uses Union-Find data structure to efficiently detect cycles. The algorithm processes edges in ascending order of weight, adding each edge to MST if it connects two different components (doesn't create cycle). Time complexity is dominated by sorting: O(E log E). With Union-Find optimizations (path compression + union by rank), union/find operations are nearly O(1) amortized.
Complexity
Time
O(E log E)
O(E log E)
O(E log E)
Space
O(V)
Applications
Industry Use
Network design (minimum cost to connect all nodes)
Circuit design (minimum wire length)
Transportation networks (roads, railways)
Clustering algorithms (single-linkage clustering)
Image segmentation
Approximation algorithms for Steiner tree
Social network analysis
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.