vizlearn
Home / Algorithms

Minimum Spanning Tree

Algorithms & Data StructuresBy Updated

Connect every vertex using the least total edge weight. Kruskal sorts edges globally; Prim grows outward from one node. Both are greedy, both are optimal — and they often pick different edges.

Controls

Edges by weight

Building the Tree

step 0

Insight

An MST connects all V vertices with exactly V−1 edges and no cycles, at minimum total weight.

edges chosen0
needed–
total weight0
rejected0

Complexity

Kruskal O(E log E)
Prim (heap) O(E log V)
Space O(V+E)

Minimum Spanning Tree

Two greedy algorithms, two different routes, the same minimum total.

Start here

A spanning tree connects every vertex of a graph using exactly V−1 edges and no cycles. The minimum spanning tree is the one with the smallest total edge weight — the cheapest way to keep everything connected.

Kruskal: Sort Globally, Add Safely

  1. Sort every edge by weight, cheapest first.
  2. Take each in turn. Add it if its endpoints are in different components; skip it if they are already connected, since that would create a cycle.
  3. Stop after V−1 edges.

The connectivity check is exactly what union-find is for — a near-constant-time "same group?" query. Kruskal is the headline application of that structure.

Notice that Kruskal's partial result is often a forest of disconnected fragments that only merge into one tree at the end.

Prim: Grow One Tree Outward

  1. Start at any vertex.
  2. Repeatedly add the cheapest edge that connects the tree to a vertex not yet in it.
  3. Stop when every vertex is included.

Prim keeps a single connected tree at all times, which is why it needs a priority queue of frontier edges rather than union-find. With a binary heap it runs in O(E log V).

Why Greedy Is Provably Correct Here: The Cut Property

Split the vertices into any two groups. The cheapest edge crossing that divide must be in some MST. That is the cut property, and both algorithms are just different ways of applying it.

Prim applies it to the cut between "in the tree" and "not in the tree". Kruskal applies it implicitly — when it adds the cheapest edge joining two components, that edge crosses the cut between them.

This is why greedy never has to backtrack, unlike the coin-change failure in the greedy module.

Which One to Use

  • Kruskal suits sparse graphs — the cost is dominated by sorting E edges. It also works naturally when edges arrive as a list.
  • Prim suits dense graphs, where E approaches V², because it never sorts everything.

If edge weights are all distinct the MST is unique, so both produce identical trees. With ties they may choose different edges — but the total weight always matches.

Real Uses

Laying cable, pipe or road networks at minimum cost; clustering (remove the k−1 most expensive MST edges to get k clusters); approximation algorithms for the travelling salesman problem; and network design generally.

The cheapest way to connect everything

Given a weighted undirected graph, a spanning tree connects all vertices using exactly V−1 edges and no cycles. A minimum spanning tree is the one with the lowest total weight.

The practical question it answers: what is the cheapest set of connections that leaves nothing isolated? Laying cable, building a road network, connecting offices — wherever connectivity is required and redundancy is not.

Two properties are worth stating, because they are what the algorithms rely on:

Exactly V−1 edges. Fewer leaves the graph disconnected; more creates a cycle, and the heaviest edge in a cycle can always be removed.

The cut property. For any way of splitting the vertices into two groups, the lightest edge crossing the split is in some MST. That single fact is what makes greedy algorithms correct here.

The MST is not necessarily unique — equal edge weights allow several — but the total weight is.

Kruskal's algorithm

Sort every edge by weight and add each one unless it would create a cycle.

def kruskal(n, edges):
    uf = UnionFind(n)
    mst, total = [], 0
    for weight, u, v in sorted(edges):
        if uf.union(u, v):            # False if u and v are already connected
            mst.append((u, v, weight))
            total += weight
            if len(mst) == n - 1:
                break                  # done
    return mst, total

The cycle check is the Union-Find union returning False. If both endpoints already share a component, adding the edge would close a cycle.

O(E log E) for the sort, plus effectively O(E) for the union operations — so sorting dominates. The algorithm builds a forest that gradually merges into one tree, which is why it does not care whether the graph is connected until the end.

Prim's algorithm

Grow a single tree from an arbitrary starting vertex, repeatedly adding the cheapest edge that reaches a new vertex.

import heapq

def prim(graph, start):
    visited = {start}
    pq = [(w, start, v) for v, w in graph[start]]
    heapq.heapify(pq)
    mst, total = [], 0

    while pq and len(visited) < len(graph):
        w, u, v = heapq.heappop(pq)
        if v in visited:
            continue                   # stale entry
        visited.add(v)
        mst.append((u, v, w))
        total += w
        for nxt, weight in graph[v]:
            if nxt not in visited:
                heapq.heappush(pq, (weight, v, nxt))
    return mst, total

Structurally this is Dijkstra's algorithm with one change: the priority is the edge weight rather than the accumulated distance from the source. Dijkstra asks "how far from the start?"; Prim asks "how cheap to attach?"

 KruskalPrim
GrowsA forest, mergingOne tree
NeedsSorted edges, Union-FindA priority queue
ComplexityO(E log E)O(E log V) with a heap
Better onSparse graphsDense graphs
Disconnected graphsProduces a forest naturallyNeeds restarting per component

For dense graphs, Prim with an adjacency matrix and a linear scan is O(V²), which beats the heap version when E approaches V².

Two algorithms, one answer, and the property that guarantees it

Kruskal and Prim look nothing alike -- one sorts all the edges globally, the other grows a single tree outward -- and they return trees of the same total weight every time. That is not a coincidence, and the cut property is what makes it inevitable.

example_01.pyPython
Output

                

                

                    
Things to try

                    
  1. Run Kruskal. Watch it consider edges in weight order and reject any that would close a cycle.
  2. Note the disconnected fragments mid-run — Kruskal builds a forest that only becomes one tree at the very end.
  3. Switch to Prim on the same graph. The tree stays connected throughout, growing outward from a single vertex.
  4. Compare the final totals. They match exactly, even when the chosen edges differ.
  5. Count the edges: always V−1. One fewer than the number of vertices — that is what makes it a tree.

                

                

                    
Worth remembering

                    
An MST connects everything with V−1 edges at minimum cost. Kruskal sorts all edges and uses union-find to reject cycles; Prim grows one tree using a priority queue. The cut property proves both greedy strategies optimal, so neither ever needs to reconsider.

                

                

                    
Where MSTs are used

                    
  • Network design. Laying fibre, power lines or pipes to connect sites at minimum cost — the original motivating problem.
  • Clustering. Build the MST, then remove the k−1 heaviest edges to get k clusters. This is single-linkage hierarchical clustering, and the MST is exactly what it computes.
  • Image segmentation. Pixels as vertices, colour difference as weight; the MST's structure reveals regions.
  • Approximation algorithms. A traveling-salesman tour built by walking the MST is within a factor of 2 of optimal, and Christofides' refinement gets to 1.5.
  • Circuit and layout design for minimum wire length.
  • Maze generation. A random spanning tree of a grid is a maze with exactly one path between any two cells.
The clustering use is the one most likely to be encountered outside a networking context, and the connection is worth remembering: MST plus cutting the heaviest edges is single-linkage clustering.

                

                

                    
MST against shortest paths

                    
A common confusion, and the distinction is sharp.
An MST minimises the total weight of the whole tree. It says nothing about the distance between any particular pair.
A shortest-path tree minimises the distance from one source to every vertex. Its total weight is generally larger than the MST's.
Concretely, in a triangle with edges A—B = 1, B—C = 1, A—C = 3: the MST is {A—B, B—C} with total 2. The shortest path from A to C in that tree is 2, which happens to match the true shortest path — but in general the path between two vertices within the MST can be much longer than their shortest path in the graph.
So: use an MST when you need cheap global connectivity; use Dijkstra when you need distances.

                

                

                    
                    
Maximum spanning tree. Negate the weights and run the same algorithm. Used in some clustering and network-reliability problems.
Bottleneck spanning tree. Minimise the heaviest edge rather than the total. The MST already achieves this — every MST is a minimum bottleneck spanning tree.
Steiner tree. Connect a subset of vertices, allowed to use others as intermediate points. NP-hard, unlike MST, and MST-based heuristics are the standard approach.
Minimum spanning forest. On a disconnected graph, Kruskal's produces one tree per component naturally.
Second-best MST. Found by trying, for each MST edge, the best replacement — useful for redundancy planning.
Borůvka's algorithm. The third classical MST algorithm, which adds the cheapest edge leaving every component simultaneously. It is the one that parallelises well, and it is the basis of modern distributed MST algorithms.

                

                

                    
Questions people ask

                    
Kruskal or Prim? Kruskal for sparse graphs and when the edges are already sorted or arriving as a list. Prim for dense graphs, especially with an adjacency matrix.
Is the MST unique? Not when edge weights tie. The total weight is unique; the edge set may not be.
Does it work with negative weights? Yes — unlike shortest-path algorithms, MST algorithms are unaffected by negative weights, because there is no notion of accumulating a path.
Does it give shortest paths? No. That is a different tree, computed by Dijkstra.
What if the graph is disconnected? Kruskal's produces a spanning forest. Prim's must be restarted from each unvisited vertex.
Why does greedy work here? The cut property: the lightest edge crossing any partition belongs to some MST, so taking it can never be a mistake.

                

                

                    
Recap in one screen

                    
  • The cheapest V−1 edges that connect every vertex without a cycle.
  • Kruskal sorts all edges and adds those that do not close a cycle, using Union-Find for the check.
  • Prim grows one tree with a priority queue — Dijkstra with edge weight instead of path distance.
  • Greedy is provably correct here because of the cut property.
  • MST minimises the total; it does not give shortest paths — and cutting its heaviest edges gives single-linkage clusters.

                

            


        

    

    


        
    



Run it in Python
Kruskal and Prim on the same weighted graph. They pick edges in completely different orders and arrive at the same total weight — which is the property worth seeing rather than being told.
mst.pyPython 3
Output
How the code works
  1. sorted(edges, key=lambda e: e[2])Kruskal's entire strategy: cheapest first, globally, ignoring where the edges are. The sort is also its dominant cost — O(E log E).
  2. if ru == rv: continueBoth ends already connected means this edge adds nothing but a cycle. Union-find answers that in near-constant time; without it the check would need a traversal per edge.
  3. heap = list(adj[start])Prim starts from one node and only ever considers edges leaving the tree it has grown. It never sees most of the graph at once, which is the opposite of Kruskal's global sort.
  4. if node in seen: continueSame lazy deletion as Dijkstra — and Prim really is Dijkstra with the priority changed from “distance from the start” to “weight of this one edge”.
  5. len(k_tree) == len(nodes) - 1Any spanning tree of V nodes has exactly V − 1 edges. Both algorithms hit that count and the same total, though the edge sets can differ when weights tie.
Change one thing
  • Print the two edge sets side by side. On this graph they match; make two edges equal in weight and they can diverge while the totals stay equal.
  • Delete edge C-F. Kruskal's very first choice changes and the whole tree reshapes.
  • Remove an edge so the graph is disconnected. Kruskal returns fewer than V − 1 edges — a spanning forest, which is often what you actually wanted.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.




Check yourself
0 of 3
Answer without scrolling back up.
  1. A spanning tree of a graph with V nodes always has:
  2. The difference between Kruskal and Prim is that Kruskal:
  3. Kruskal uses union-find to:





 Cheat sheet
Minimum Spanning Tree
Connect every vertex using the least total edge weight. Kruskal sorts edges globally; Prim grows outward from one node. Both are greedy, both are optimal — and they often pick different edges.
ALGORITHMS · vizlearn.in/dsa/minimum_spanning_tree.html
More in Algorithms
AlgorithmsTwo PointersAlgorithmsSliding WindowAlgorithmsGreedy AlgorithmsAlgorithmsBacktracking Search Method
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact