Skip to content
Tutorials Center
My learning

Topics

Lesson 139 of 225 ยท Shortest Paths and Spanning Trees

Minimum Spanning Trees: Kruskal and Prim

Learn minimum spanning trees: cut and cycle properties, Kruskal's algorithm with union-find, Prim's algorithm with a heap, clustering, and when to use each.

Imagine you must connect six villages with roads, and each possible road has a construction cost. You want every village reachable from every other, and you want the total cost as low as possible. You would never build a road that closes a loop, because removing any road from a loop keeps everything connected and saves money. What you end up with is a tree, and the cheapest one is called the minimum spanning tree (MST).

The same shape of problem appears when laying cables or pipes, designing circuit boards, grouping similar items into clusters, and approximating hard problems like the traveling salesman problem. Two classic greedy algorithms solve it: Kruskal's (take the cheapest edges that do not form a cycle) and Prim's (grow one tree outward from a start vertex). This lesson explains why greedy choices are safe here, builds both from scratch, and compares them.

Definitions

  • A spanning tree of a connected, undirected graph with V vertices is a set of V - 1 edges that connects all vertices without any cycle.
  • In a weighted graph, the minimum spanning tree is the spanning tree with the smallest total weight.
  • If the graph is not connected, there is no spanning tree, but each component has its own; together they form a spanning forest.
  • The MST is not always unique. If several edges share the same weight, different trees can tie. When all weights are distinct, the MST is unique.
TEXT
edges: A-B 4, A-C 2, B-C 5, B-D 10, C-D 3, C-E 8, D-E 7, D-F 6, E-F 1

   A ---4--- B
   |
   2                     MST = {E-F 1, A-C 2, C-D 3, A-B 4, D-F 6}
   |                     total weight 16, five edges for six vertices
   C ---3--- D
             |
             6
             |
        E ---1--- F

Beware of two common confusions. An MST minimizes the total weight of the tree, not the distance between any two vertices; the path between two vertices in an MST can be much longer than the shortest path in the graph. And an MST is for undirected graphs; the directed version is a different, harder problem.

Why greedy works: the cut and cycle properties

Both algorithms rely on two facts. They are easy to believe after a moment of thought.

Cut property. Split the vertices into two non-empty groups in any way (a "cut"). Among the edges that cross from one group to the other, the cheapest one belongs to some MST (to every MST if it is the unique cheapest). Intuition: any spanning tree must cross the cut somewhere; if it used a more expensive crossing edge instead, swapping in the cheapest crossing edge would give a tree that is no worse.

Cycle property. In any cycle, the most expensive edge (if it is strictly the most expensive) belongs to no MST. Intuition: you can always remove it, keep everything connected through the rest of the cycle, and lower the cost.

Kruskal uses the cycle property (skip edges that would close a cycle). Prim uses the cut property (the cut is "inside the tree" versus "outside"). The following brute-force check makes the definitions concrete: try every set of V - 1 edges and keep the best.

Python Brute force: try every set of V-1 edges

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Of the 126 subsets, 55 are spanning trees, and exactly one of them has the minimum weight. This works only for tiny graphs. Choosing V - 1 edges out of E gives "E choose V - 1" subsets, which explodes quickly. The greedy algorithms below find the same tree in near-linear time.

Kruskal's algorithm

  1. Sort all edges by weight, cheapest first.
  2. Go through them in order. Keep an edge if it connects two vertices that are not yet connected; skip it otherwise.
  3. Stop when you have V - 1 edges.

To check "are these two vertices already connected?" quickly, use union-find: find returns a component's representative and union merges two components. Both are almost O(1).

Python Kruskal with a trace of every decision

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow the trace. The edge B-C (weight 5) is skipped: A is already linked to both B and C, so B and C are connected, and adding B-C would make a triangle. The edge D-F (weight 6) is accepted because D lies in the big component {A, B, C, D} and F in {E, F}; it is the cheapest edge that joins them, which is the cut property in action. The loop stops as soon as five edges are chosen, so D-E, C-E and B-D are never looked at.

Complexity. Sorting costs O(E log E), which equals O(E log V) because E is at most Vยฒ. The union-find work is O(E ยท ฮฑ(V)), where ฮฑ is the inverse Ackermann function, below 5 for any input you will ever see. Total O(E log V) time and O(V) extra space. If the weights are small integers you can sort with counting sort and get closer to linear.

Prim's algorithm

Prim's algorithm grows a single tree.

  1. Start from any vertex; mark it as in the tree.
  2. Repeatedly pick the cheapest edge that connects a vertex in the tree to a vertex outside it, and add that edge and vertex.
  3. Stop when all vertices are in the tree.

Finding the cheapest crossing edge quickly is a job for a priority queue. The simplest version is "lazy": push every edge leaving a newly added vertex onto a heap, and when you pop an edge whose far end is already in the tree, just discard it.

Python Prim with a heap (lazy version)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The tree grows A, then C (cost 2), then D (3), then B (4), then F (6), then E (1). It reaches the same total as Kruskal, though the edges were chosen in a different order. Prim's code looks almost like Dijkstra: the only change is the heap key. Dijkstra keys by the total distance from the start (dist[u] + w); Prim keys by the single edge weight w.

Complexity. Each edge is pushed at most twice, and each heap operation is O(log E) = O(log V), so O(E log V) with a binary heap. Space is O(E) for the lazy heap.

Dense graphs: the O(Vยฒ) array version

If the graph is dense (E close to Vยฒ), skip the heap. Keep an array best[v] with the cheapest edge connecting v to the tree, and each round scan the array for the smallest unused entry. That is V rounds of O(V), so O(Vยฒ) with no log factor and no heap. It is the best choice when the graph is given as a matrix or is complete, as in the next example.

Python Prim in O(V squared) for points on a plane

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

A complete graph on n points has n(n - 1) / 2 edges, so storing and sorting them for Kruskal would be O(nยฒ log n), while this version is O(nยฒ) with almost no memory.

Kruskal or Prim?

Kruskal Prim (heap) Prim (array)
Idea add cheapest edge that makes no cycle grow one tree grow one tree
Needs edge list + union-find adjacency list + heap matrix or distance function
Time O(E log V) O(E log V) O(Vยฒ)
Best for sparse graphs, edge lists, early stopping general graphs dense or complete graphs
Disconnected graph gives a spanning forest only the start's component only the start's component

Both are correct for any connected graph. In practice Kruskal is the shorter program when the input is an edge list; Prim is natural when you already have adjacency lists or a distance function.

Variations you will meet

Maximum spanning tree. Sort edges in descending order (Kruskal) or use a max-heap (Prim). Alternatively negate every weight.

Clustering with Kruskal. Stopping Kruskal when k components remain gives the grouping that maximizes the smallest gap between groups. It is a simple form of single-linkage clustering.

Python Kruskal stopped early gives k clusters

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Bottleneck paths. The path between two vertices inside an MST minimizes the largest single edge along the path, among all paths in the graph. That is handy for questions like "what is the smallest cable capacity that connects A to B?".

Second-best MST and "must include edge" questions. Add the extra edge to the MST, which creates exactly one cycle, then remove the heaviest other edge on that cycle.

Is this edge in some minimum spanning tree?

Given an edge (u, v, w), can it belong to at least one MST? Two quick tests follow from the cycle property:

  • Let d be the smallest possible bottleneck (largest edge on the path) from u to v using other edges only. If d < w, a cheaper detour exists and the edge is in no MST.
  • If d == w, the edge ties with a detour; it is in some MST (but not necessarily all).
  • If d > w or u and v are not otherwise connected, the edge is in every MST (it is a necessary bridge of the cheapest structure).

A simple way to compute this: run Kruskal, but process edges in groups of equal weight. Before adding a group, check each edge of the group: if its endpoints are already connected by strictly lighter edges, it can never be used; otherwise it can. Then union the group.

Python Which edges can appear in an MST?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Edges (1, 2, 2) and (0, 2, 2) tie: either one can complete the connection to vertex 2, so both are fine, but a tree contains only one of them. The edge (1, 3, 4) is rejected because 1 - 2 - 3 already connects its endpoints with lighter edges. Time O(E log E).

Common mistakes

  • Running it on a directed graph. MST is defined for undirected graphs. Directed spanning trees (arborescences) need different algorithms.
  • Forgetting disconnected input. Check that you ended with V - 1 edges; fewer means the graph was not connected.
  • Confusing MST with shortest paths. Prim differs from Dijkstra only in the heap key, but the results are different trees with different goals.
  • Naive cycle checks in Kruskal. Using a DFS per edge makes it O(E ยท V). Use union-find.
  • Assuming the MST is unique. Ties can produce different, equally good trees. Compare total weights in tests, not edge lists.
  • Skipping stale heap entries incorrectly. In lazy Prim, check whether the far vertex is already in the tree after popping.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How many edges does a spanning tree of a connected graph with 10 vertices have?

    A tree on V vertices has V - 1 edges: enough to connect everything, too few to make a cycle.
  2. 2. Which property justifies skipping an edge in Kruskal's algorithm when it joins two already-connected vertices?

    Adding the edge would create a cycle. Since the edges are processed in increasing order, it is the heaviest edge of that cycle, so it can be dropped.
  3. 3. What is the time complexity of Kruskal's algorithm with sorting and union-find?

    Sorting the edges costs O(E log E) = O(E log V). The union-find operations add only O(E * alpha(V)), which is almost linear.
  4. 4. What is the difference between Prim's and Dijkstra's heap keys?

    Prim wants the cheapest edge leaving the tree. Dijkstra wants the vertex closest to the source, so it adds the path length so far.
  5. 5. When is the O(V^2) array version of Prim preferred?

    With about V^2 edges, a heap adds a log factor and memory for nothing; scanning an array each round costs O(V) and totals O(V^2).

Summary

  • A spanning tree has V - 1 edges and no cycle; the MST minimizes total weight and exists only for connected undirected graphs.
  • Cut property (cheapest crossing edge is safe) and cycle property (the heaviest edge of a cycle is not needed) make greedy choices correct.
  • Kruskal: sort edges, add each one that joins two different components (union-find). O(E log V).
  • Prim: grow one tree using a heap of crossing edges. O(E log V), or O(Vยฒ) with an array for dense graphs.
  • Stop Kruskal at k components for clustering; negate or reverse the order for a maximum spanning tree.
  • MSTs may tie, so test by total weight.

Next: Strongly Connected Components