Skip to content
Work Practice Products Coding interviews Machine learning coding Quant developer HFT course Blog Method Why me About Enquire Book a call

Coding · Graphs

Minimum spanning trees: Kruskal's and Prim's algorithms

Lesson · 10 min read · Graphs · Union-find and spanning trees

Connect every node at the least total cost. Take the cheapest edge that does not close a cycle, and repeat.

The problem

Given a connected, weighted, undirected graph, a spanning tree is a set of n − 1 edges that connects every node with no cycle. A minimum spanning tree (MST) is one with the smallest total weight: the cheapest way to lay cable between offices, to connect points on a circuit board, or to link data centres.

425362718ABCDEF
Six sites and the cost of linking each pair that can be linked.

Why greedy works: the cut property

Split the nodes into any two groups. Among the edges that cross between them, the cheapest one belongs to some minimum spanning tree. (If a tree avoided it, adding it would create a cycle crossing the split twice; removing the other crossing edge on that cycle gives a tree that is no more expensive.) Both standard algorithms are this property applied repeatedly.

Kruskal's algorithm

kruskal(n, edges)

  1. Sort the edges by weight.
  2. For each edge (u, v, w) in that order: if union(u, v) succeeds (they were in different groups), keep the edge and add w.
  3. Stop after n − 1 edges. If fewer were kept, the graph is not connected.

Prim's algorithm

prim(graph, s)

  1. Start the tree at s. Push every edge from s into a min-heap.
  2. Pop the cheapest edge; if it leads to a node already in the tree, skip it.
  3. Otherwise add that node and its edge to the tree, and push its edges. Repeat until all n nodes are in.

Kruskal, step by step

Edges are taken from cheapest to most expensive; union-find rejects any edge whose ends are already joined.

Kruskal's algorithm on the six sites.

  1. Step 1 / 6
    425362718ABCDEF

    Sort the edges by weight: 1, 2, 2, 3, 4, 5, 6, 7, 8. Every node is its own group.

  2. Step 2 / 6
    425362718ABCDEF
    total1edges1

    E–F (1): it joins two different groups, so take it. Total 1.

  3. Step 3 / 6
    425362718ABCDEF
    total3edges2

    A–C (2): it joins two different groups, so take it. Total 3.

  4. Step 4 / 6
    425362718ABCDEF
    total5edges3

    D–E (2): it joins two different groups, so take it. Total 5.

  5. Step 5 / 6
    425362718ABCDEF
    total8edges4

    B–D (3): it joins two different groups, so take it. Total 8.

  6. Step 6 / 6
    425362718ABCDEF
    total12edges5

    A–B (4): it joins two different groups, so take it. Total 12. 5 edges join all 6 nodes: that is a minimum spanning tree, weight 12.

in the treerejected: would close a cycle

Which one to use

TimeKruskal O(m log m); Prim O(m log n)
SpaceO(n + m)

Kruskal is the natural choice when you are given a list of edges, and its union-find makes it easy to stop early or to work with groups. Prim suits an adjacency list, and on a complete graph with n points it can be written in O(n²) with no heap at all, which beats sorting all n²/2 edges.

The problem at the end of this module, connecting points on a plane, is that dense case: every pair of points is an edge.