A facilities team must trench fiber between five offices so every office can reach every other, at minimum total cost. The first version ran Dijkstra from HQ and kept the shortest-path tree. A cheap cross-campus duct sat unused because both ends already had a path from HQ. That path was shortest from HQ. It was not cheapest for the whole mesh. Nobody asked for distances from a source. They asked to connect everyone.

Kruskal sorts every edge cheapest first, skips a pair already in the same component, and unions the rest — until n-1 edges, or the list runs out. The layout is an undirected weighted edge list (Graphs). The membership test is Union-Find. Families and the catalog live on the Algorithms Roadmap. Prim is the seed-growth cousin — named once, not walked. This is not a shortest path from s, and not a reason to DFS-detect a cycle you can ask find about.

The job is a tree, not a path from s

An MST connects all vertices at minimum total edge weight. Undirected. No cycles. n vertices need n-1 edges if the graph is connected; fewer if it is not (a minimum spanning forest). Negative weights are legal: cheaper is cheaper. The job is the sum of accepted edges, not dist[v] from a source.

A shortest-path tree from HQ can keep an expensive spur that Dijkstra settled early and skip a cheap link whose endpoints were already reachable. Different objective. Dijkstra and Bellman-Ford answer “from s”; Kruskal answers “the whole mesh.”

A DFS or BFS tree is a spanning tree of some weight. The algorithm did not look at weights. A spanning tree is not an MST just because it connects everyone.

Note: Directed graphs do not have this MST. Kruskal’s “both ends, one undirected edge” is the layout. An adjacency list of one-way links is a different object.

Sort cheapest, skip same component, union

Start with every vertex in its own component. Sort the edge list by weight, ascending. Repeatedly:

  1. Peek the next cheapest unused edge u — v of weight w.
  2. Skip it if find(u) == find(v) — already the same component; that edge would cycle.
  3. Accept it otherwise: record the edge, union(u, v).
  4. Stop at n-1 accepted edges (a tree) or when the list is exhausted (a forest).

You do not grow from a seed. You consider every edge in cost order and keep a link only when it merges two components. The growing structure is a forest that becomes a tree if the graph is connected.

A cycle in that forest is exactly “same component.” Cycle detection walks the graph to name a back edge; Kruskal never walks.

A walked pass, including two skipped edges

Five vertices. The cheap spine A—B—C—D—E is the MST. The chords A—C and B—D look tempting in the middle of the sort and lose because their ends already share a component. C—E is cheaper than nothing left to merge once D—E lands.

undirected, weighted:

  A --1-- B --2-- C --3-- D --6-- E
   \      |      /
    4     5     +--7-- E     (A—C=4, B—D=5, C—E=7)

ids:    A=0 B=1 C=2 D=3 E=4
sorted: (A,B,1) (B,C,2) (C,D,3) (A,C,4) (B,D,5) (D,E,6) (C,E,7)

take (A,B,1)   union A,B     {A,B} {C} {D} {E}
take (B,C,2)   union B,C     {A,B,C} {D} {E}
take (C,D,3)   union C,D     {A,B,C,D} {E}
skip (A,C,4)   find(A)==find(C)
skip (B,D,5)   find(B)==find(D)
take (D,E,6)   union D,E     {A,B,C,D,E}   4 edges — stop
               (C,E,7) never considered

MST:    A—B, B—C, C—D, D—E
weight: 1+2+3+6 = 12
not:    A—C (4) or B—D (5) — same component, would cycle

Each accepted edge merges two components. Each skip is a chord of the forest already built. Empty graph: zero edges, n components, forest of isolated vertices. Drop D—E and C—E and the list exhausts at three edges: E stays its own component.

Union-Find is the API, not the lecture

Kruskal owns the sort and the accept/skip policy. Union-Find only answers would this merge two components? Call find on both ends; union when they differ. The parent array, the two tweaks that keep those calls cheap, and the class you should ship already live in the Union-Find post. This post consumes that API.

union returning false is the skip. You do not need an adjacency list of the growing tree to ask the same question.

Java sketch

Edges as record Edge(int u, int v, int w). Sort by w. A compact find / union so the loop compiles in your head — use the Union-Find post’s class in real code. Collect accepted edges. Stop at n-1 or when the list ends.

record Edge(int u, int v, int w) {}

static final class UF {
    final int[] p;
    UF(int n) {
        p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
    }
    int find(int x) {
        while (p[x] != x) {
            x = p[x];
        }
        return x;
    }
    boolean union(int a, int b) {
        int ra = find(a), rb = find(b);
        if (ra == rb) {
            return false; // already same component
        }
        p[ra] = rb;
        return true;
    }
}

static List<Edge> kruskal(int n, List<Edge> edges) {
    List<Edge> sorted = new ArrayList<>(edges);
    sorted.sort(Comparator.comparingInt(Edge::w));
    UF uf = new UF(n);
    List<Edge> mst = new ArrayList<>();
    for (Edge e : sorted) {
        if (mst.size() == n - 1) {
            break;
        }
        if (uf.union(e.u(), e.v())) {
            mst.add(e);
        }
    }
    return mst; // n-1 edges, or a forest if disconnected
}

Map real vertex keys onto 0 … n-1 the same way the Union-Find post does. The sketch assumes ids are already dense. Sum e.w() on the returned list for the MST weight.

Note: Self-loops are same-component immediately — skip. Parallel undirected edges: the sort keeps the cheapest copy first; later twins skip. Directed “both ways with different weights” is not this layout.

Complexity

Let V be vertices, E edges. The sort dominates. Each edge then pays a find / union.

TimeO(E log E) from the sort; then E membership tests
Extra RAMSorted copy, parent [V], at most V-1 accepted edges
StopV-1 edges (tree) or list exhausted (forest)
Dense vs sparseKruskal likes a sorted edge list (sparse); Prim may win on dense

Glossary and the Big-O reading live on the hub. The bill that kills the fiber plan is the wrong job (a shortest-path tree from HQ), not a fancier sort.

If the graph is disconnected you still scan every edge. The return value is a forest; check mst.size() == n - 1 if you required a single tree.

When not to run Kruskal

Skip it when:

  • The graph is directed. MST is an undirected contract. One-way links are a different object.
  • You needed a shortest path from s. Dijkstra (non-negative) or Bellman-Ford (negatives allowed). Kruskal’s total is not dist[t].
  • The question is a negative cycle on a shortest-path job. Wrong algorithm family. Kruskal will happily accept a negative edge in an MST; it will not tell you a walk can get arbitrarily cheap.
  • The graph is dense and you already grow from a seed. Prim may win — one sentence, that post owns it.

Do not run Kruskal to answer “how far is t from s?” Do not DFS the growing forest to detect the cycle Union-Find already flagged.

Also skip it when any spanning tree will do (connectivity only): a DFS tree is enough and does not sort.

JDK: a sort and a Union-Find, not a Kruskal class

There is no java.util.Kruskal. The library pieces are:

  • Sort: List.sort(Comparator.comparingInt(Edge::w)) (or Arrays.sort)
  • Layout: a List<Edge> as in the graph post, undirected
  • Membership: a Union-Find you write — the other post

Prefer the sorted edge list when E is the thing you already have (sparse mesh, trench table, edge dump). Reach for Prim when the input is a dense matrix and you grow from a seed.

Do not scan neighbors on every candidate to “see if u can reach v.” Do not sort vertices. Do not build an adjacency list only to ask same-component.

Cheat sheet

Job:        MST (or forest): connect vertices, min total weight, undirected
Procedure:  sort edges by w; skip if find(u)==find(v); else accept + union
Stop:       n-1 edges, or edges exhausted (disconnected → forest)
Skip:       same component = that edge would cycle
UF:         consume find/union; do not re-teach the parent-array lecture
Prim:       seed-growth cousin — not this post
SP from s:  Dijkstra / Bellman-Ford — wrong job
JDK:        List.sort + Union-Find you write; no Kruskal type
Do not:     shortest-path tree from HQ; DFS-detect the cycle find already saw

Do:

  • Sort the whole undirected edge list. Accept a link only when it merges components.
  • Stop at n-1 or at the end of the list. Count edges if you required one tree.
  • Call Union-Find; point production code at that class.

Don’t:

  • Treat a shortest-path tree from HQ as an MST when the job is total trench cost.
  • Run this on a directed graph, or to answer dist[s ⇝ t].
  • Walk the forest to detect a cycle find already reported.
  • Re-implement Union-Find’s two tweaks here — they are not Kruskal’s job.

Wrap-up

Kruskal is an MST by cheapest legal edge: sort, skip same component, union, stop at n-1 or when the list ends. The sort is the algorithm. Union-Find is the membership API. The result is a tree (or a forest), not distances from a source. Use Dijkstra or Bellman-Ford when the question is a path from s. Use a DFS tree when any spanning tree will do. Hand-roll the sketch when the edges are undirected, weighted, and the assignment is minimum total weight.

The next procedure in this wave is the same MST from a seed: grow with a heap of crossing edges instead of sorting every edge.

Next optional step in the series Grow an MST from a seed vertex instead of sorting every edge. Prim: Grow an MST From a Seed Vertex