Kruskal's algorithm

Prerequisites

• Undirected weighted graphs (see representations).
• Union-Find, to detect loops fast.
• Sorting (see Sorting).

The analogy

How it works

Precondition: an undirected, connected, weighted graph. Negative weights are fine. On a disconnected graph it gives a minimum spanning forest.

Start with the edge list by hand

Edges sorted by weight: A–B 1, C–D 2, B–C 3, A–C 4, B–D 5. At the start every town is its own group. Predict, then open "Check".

Finish the picture: why greedy works

Suppose someone claims a cheaper tree without A–B, the cheapest edge.

• Add A–B to their tree. Predict what appears.
  Check

  A cycle: their tree already connects A and B some other way.

• Remove another edge of that cycle. Predict the new total.
  Check

  Every other edge on the cycle costs more than 1, so swapping it for A–B makes the tree cheaper or equal. So the cheapest edge can always be in a minimum tree; the same argument repeats for each step.

The rule in plain words

Sort the edges by weight. Start with every vertex in its own group.

For each edge in order: if its ends are in different groups, add it to the tree and merge the groups; otherwise skip it. Stop after $V - 1$ edges.

The code

Read this code after you have done the run by hand. It will make more sense.

int find(int parent[], int x) {                     /* group representative */
    while (parent[x] != x) x = parent[x];
    return x;
}

int kruskal(int n, int m, int eu[], int ev[], int ew[]) {   /* edges sorted by weight */
    int parent[100];
    for (int i = 0; i < n; i++) parent[i] = i;          /* every vertex alone */
    int total = 0;
    for (int j = 0; j < m; j++) {
        int a = find(parent, eu[j]), b = find(parent, ev[j]);
        if (a != b) { parent[a] = b; total += ew[j]; }   /* joins two groups: keep */
    }
    return total;                                       /* weight of the MST */
}

flowchart TD
  A["sort edges by weight"] --> B["take the next cheapest edge u-v"]
  B --> C{"u and v in the same group?"}
  C -->|yes| D["skip: it would close a cycle"]
  C -->|no| E["keep it, merge the groups"]
  D --> F{"V - 1 edges kept?"}
  E --> F
  F -->|no| B
  F -->|yes| G["done: minimum spanning tree"]
          

How fast is it?

Sorting dominates; then each edge needs two finds and maybe one union, nearly constant with a good Union-Find:

$\log E$ and $\log V$ differ by at most a factor of 2, because $E < V^2$.

Common mistakes

• Rejecting an edge just because one end is already in the tree; only reject when both ends are in the same group.
• Forgetting to sort the edges first.
• Running it on a directed graph: minimum spanning trees are for undirected graphs.

Try it yourself

Did you know?

Key points to remember

If you remember one thing from each line, remember the because.

• Kruskal takes the cheapest safe edge because the cheapest edge between two groups is always part of some minimum tree.
• It rejects edges inside one group because they would close a cycle.
• It runs in $O(E \log E)$ because sorting the edges dominates.
• Union-Find makes the cycle check fast because two finds tell whether two vertices are already connected.
• A spanning tree has $V - 1$ edges because each kept edge merges two groups, from $V$ groups down to 1.

Self-check questions

Answer these in order, out loud. They follow the page, so your answers become the script of your video.

1. How is Kruskal like building roads on a budget?
   Sample answer

   You build the cheapest road first and keep going in order of cost, skipping any road between villages that are already connected.

2. Walk through Kruskal on A–B 1, C–D 2, B–C 3, A–C 4, B–D 5.
   Sample answer

   Accept A–B, accept C–D, accept B–C (joins the two groups), reject A–C and B–D (cycles). Total 6.

3. Why does the code compare find(parent, u) with find(parent, v) instead of checking the edge directly?

   A good answer mentions indirect connections.

   Sample answer

   Two vertices can be connected through other edges without an edge between them; only their group representatives reveal whether a new edge would close a cycle.

4. So what is Kruskal's algorithm, in one sentence?
   Sample answer

   It builds a minimum spanning tree by taking edges from cheapest to most expensive and keeping each one that connects two different components.

5. Why is it safe to always take the cheapest edge between two groups?

   A good answer uses the swap argument.

   Sample answer

   If a minimum tree didn't use it, adding it creates a cycle with a more expensive edge; swapping them gives a tree that's no more expensive. So some minimum tree contains it.

6. What does Kruskal cost, and which step dominates?
   Sample answer

   $O(E \log E)$, dominated by sorting the edges; Union-Find work is almost linear.

7. When would you choose Prim instead?
   Sample answer

   On dense graphs stored as matrices, where Prim's $O(V^2)$ array version avoids sorting $O(V^2)$ edges.

8. If you had to teach this to a friend in 2 minutes, what would you leave out, and why?
   Sample answer

   I'd leave out the swap proof and the $\alpha(V)$ term. I'd keep the road-budget analogy, the five-edge trace with two rejections, and "sort edges, skip cycles, $O(E \log E)$".

External resources

• VisuAlgo: Minimum spanning tree: run Kruskal and Prim on the same graph.
• GeeksforGeeks: Kruskal's algorithm: code with Union-Find.
• Wikipedia: Kruskal's algorithm: proof and complexity.

Videos

• YouTube search: Kruskal's algorithm: pick a short walkthrough.