Vibe Engines Learn
ALGORITHMS · 12  /  KRUSKAL'S MST

The Cheapest Grid.

Eight towns, a price on every possible cable. Connect them all for the least total cost by always laying the cheapest cable that doesn't close a loop — and let Union-Find catch the loops for you.

THE GIST · 20 SECONDS

Kruskal's algorithm finds a minimum spanning tree — the cheapest set of edges that connects every node with no cycles. It's greedy: sort all edges by weight, then walk from cheapest to dearest, adding each edge unless it would form a cycle. A Union-Find answers "already connected?" in near-constant time. Stop at n − 1 edges — done.

  • MSTcheapest cycle-free connect
  • Greedyalways take the cheapest
  • Cyclea loop — reject it
  • Union-Find"already connected?"

Hit Step to weigh the next cheapest cable — or Play and watch the grid wire itself up for the least total cost.

UNDER THE HOOD

What you just played, written down

Sort once, then be greedy: take the cheapest edge that keeps the pieces separate. A Union-Find turns "would this close a loop?" into a constant-time check.

How Kruskal's thinks — four moves

  1. Sort every edge by weight. Cheapest first. This one sort is where all the cost goes.
  2. Start with n islands. Each node is its own component in a Union-Find — nothing connected yet.
  3. Take it if it merges two islands. For each edge in order, if its endpoints are in different components, add it and union them.
  4. Skip it if it's a loop. If the endpoints already share a leader, the edge would form a cycle — reject it and move on.
WHY GREEDY IS ACTUALLY OPTIMAL

The cut property: for any way you split the nodes into two groups, the cheapest edge crossing that split is safe to include in some MST. Kruskal always adds the cheapest edge joining two separate pieces — exactly such a safe edge.

The whole thing in code

def kruskal(n, edges):        # edges: [u, v, w]
    edges.sort(key=lambda e: e[2])   # cheapest first
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    total = 0
    for u, v, w in edges:
        ru, rv = find(u), find(v)
        if ru != rv:              # different islands?
            parent[ru] = rv       # union - take the edge
            total += w
        # else: same island -> cycle -> skip
    return total
TIMEO(E log E)dominated by the sort
SPACEO(V)the Union-Find
THE UNION-FIND IS THE WHOLE TRICK

Without it, checking "does this edge form a cycle?" means a graph search each time. Union-Find does it in O(α) — effectively constant — so the algorithm's cost collapses to just the initial sort.

⚠ Needs a connected graph

If the graph is disconnected, Kruskal's can't produce a single spanning tree — it builds a minimum spanning forest instead, one tree per connected component.

↔ Kruskal vs Prim

Kruskal sorts all edges and merges a forest (great for sparse graphs / edge lists). Prim grows one tree from a start node with a priority queue (often better for dense graphs).

★ Where it's used

Laying cable, roads, and pipelines for least cost, network design, clustering (cut the most expensive MST edges), and approximate solutions to harder tour problems.

SOLVE IT YOURSELF

Solve it: minimum spanning tree weight

This one is yours to write — in Python or TypeScript, running for real in your browser. Sort the edges, union the cheapest that don't form a cycle, and return the total weight. Edit the stub, hit Run (or ⌘/Ctrl + Enter), and watch the hidden tests. Stuck? the hints are below and Reveal solution is one click away.

YOUR TASK

Implement kruskal(n, edges): n nodes (0…n-1) and edges as [u, v, w] triples. Return the total weight of a minimum spanning tree using Kruskal's algorithm (assume the graph is connected).

HINTS — 4 IDEAS
  1. Sort the edges by weight ascending — the whole algorithm hinges on this order.
  2. Keep a Union-Find: parent[i] = i, and find(x) walks to the root (with path compression).
  3. For each edge, if find(u) != find(v), union them and add w to the total.
  4. If they're already in the same set, the edge is a cycle — skip it.
CPython · WebAssembly
QUICK CHECK

Did it stick?

FAQ

Kruskal's, answered

What is Kruskal's algorithm?

A greedy way to build a minimum spanning tree: sort every edge by weight, then add each cheapest edge unless it forms a cycle. After n − 1 edges, all nodes are connected for the least total weight.

What is a minimum spanning tree?

A subset of edges that connects all n nodes with exactly n − 1 edges and no cycles, at the smallest possible total weight — the cheapest way to wire everything together.

How does it use Union-Find?

Before adding an edge it checks find(u) == find(v). Equal leaders mean the two are already connected, so the edge would close a cycle and is skipped; otherwise union merges them and the edge joins the tree.

What's the time complexity?

O(E log E), dominated by sorting the edges. The Union-Find work across all edges is only O(E · α(V)) — effectively linear.

Kruskal vs Prim?

Both are greedy MST algorithms. Kruskal sorts all edges and merges a forest (good for sparse graphs); Prim grows one tree from a start node with a priority queue (good for dense graphs).

RESULT

—

Next → that cycle check you kept using is Union-Find, and growing one tree instead of a forest is Prim's algorithm. Same goal, different greedy.

Finished this one? 0 / 17 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →