1. Sort by weight
Process the cheapest edges first so each pick is the best available.
edges.sort((a, b) => a[2] - b[2])Typorithm · medium
Kruskal's MST
▷ Interactive algorithm labkruskal-mstgraph-algorithmsunion-findgreedysorting
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Kruskal's MST
Graph Algorithms
Sort edges by weight, then greedily add each edge whose endpoints are in different sets via Union-Find, stopping at n-1 edges.
Kruskal's builds a minimum spanning tree by considering edges from cheapest to most expensive.
A Union-Find structure answers whether two endpoints already sit in the same component.
An edge is kept only if union joins two different sets — that guarantees no cycle forms.
Preparing algorithm lab…
01
Sort all edges by weight ascending.
02
union returns true = different sets, so add the edge.
03
Stop once n-1 edges are chosen.
function kruskalMst(n, edges) {
edges.sort((a, b) => a[2] - b[2]);
const dsu = new UnionFind(n);
let total = 0;
let used = 0;
const tree = [];
for (const [a, b, weight] of edges) {
if (dsu.union(a, b)) {
tree.push([a, b, weight]);
total += weight;
used += 1;
if (used === n - 1) break;
}
}
return used === n - 1 ? { total, tree } : null;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Disjoint sets
Each node starts in its own set; the DSU tracks which nodes are connected.
const dsu = new UnionFind(n)3. Different sets
union returns true only when the endpoints were in different sets, so adding the edge cannot form a cycle.
if (dsu.union(a, b))4. Add safe edge
A safe edge joins two components and belongs in the spanning tree.
tree.push([a, b, weight])5. Stop at n-1
A spanning tree on n nodes has exactly n-1 edges, so we can stop early.
if (used === n - 1) breakA complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.