Lesson 1 · Advanced graph algorithms

Minimum Spanning Tree

A Minimum Spanning Tree (MST) is a subset of edges in a connected, weighted, undirected graph that connects all vertices without any cycles and with the lowest total edge weight.

What an MST Is, and What It Is Not

A spanning tree of a connected undirected graph is a subset of edges that touches every vertex, contains no cycle, and keeps the graph connected. Any such subset has exactly V−1 edges — one fewer than the vertex count, which is the defining property of a tree.

A minimum spanning tree is the spanning tree whose edge weights sum to the smallest possible total. It exists only if the graph is connected; a disconnected graph has no spanning tree, only a minimum spanning forest with one tree per component.

The confusion worth clearing immediately is between an MST and shortest paths, because they sound similar and are examined together. An MST minimises the total weight of the whole tree. A shortest path minimises the distance between two specific vertices. These are different objectives and generally give different answers.

Concretely: the path between two vertices within an MST is frequently longer than their true shortest path in the graph. The MST may have routed around a heavy direct edge to save weight elsewhere in the tree, which is optimal for the total and suboptimal for that pair. So an MST is the wrong structure for routing and the right one for construction.

That distinction determines the applications. An MST answers 'connect all of these as cheaply as possible' — laying cable to reach every building, wiring a circuit, building a road network on a budget. Each is a total-cost question, not a travel-time question.

Uniqueness is worth stating precisely: if all edge weights are distinct, the MST is unique. If weights tie, several minimum spanning trees may exist with the same total, and different algorithms — or the same algorithm with a different tie-break — may return different ones. All are equally valid.

Touches every vertex, has V−1 edges, contains no cycle
Requires a connected graph; otherwise you get a spanning forest
Minimises the tree's total weight, not any pairwise distance
Unique when all weights differ; ties allow several valid answers

The Cut Property

Both standard algorithms are greedy, and both are correct for the same reason. Stating that reason is what turns two memorised procedures into one idea.

A cut is any partition of the vertices into two non-empty sets. An edge crosses the cut if its endpoints lie on opposite sides.

The cut property: for any cut, the lightest edge crossing it belongs to some minimum spanning tree. If that edge is strictly lighter than every other crossing edge, it belongs to every minimum spanning tree.

The proof is an exchange argument and is short enough to give in full. Let e be the lightest edge crossing some cut, and suppose an MST T does not contain e. Adding e to T creates exactly one cycle. That cycle must cross the cut a second time, so it contains another crossing edge f. Since e is the lightest crossing edge, weight(e) ≤ weight(f). Removing f and keeping e yields a spanning tree no heavier than T — so an MST containing e exists.

That single property justifies every choice both algorithms make. They differ only in which cut they apply it to.

Prim's applies it to the cut separating the tree built so far from everything else. The cheapest edge leaving the tree is the lightest edge crossing that cut, so taking it is safe.

Kruskal's applies it to the cut separating the component containing one endpoint of the candidate edge from the rest. Because edges are considered in increasing weight order, the current edge is the lightest one crossing that cut among those not yet rejected.

Recognising both as instances of one property is the answer an examiner is looking for, and it is more useful than remembering the two procedures separately.

The lightest edge crossing any cut is in some MST
Proof: adding it creates a cycle that must re-cross the cut; swap them
Prim's cut separates the growing tree from the rest
Kruskal's cut separates the components an edge would join

Kruskal's and Prim's

Kruskal's algorithm works globally on edges. Sort all E edges by weight ascending, then consider each in turn: add it if its endpoints lie in different components, skip it if they are already connected, since adding it would create a cycle. Stop after V−1 edges have been accepted.

The component test is the implementation question, and the answer is union-find. find(u) == find(v) decides whether the endpoints are already connected, and union(u, v) merges the components when the edge is accepted. With union by rank and path compression, both are effectively O(α(n)) — constant for practical purposes.

Total cost is O(E log E), dominated entirely by the sort. Since E ≤ V², log E is at most 2 log V, so this is equivalently O(E log V).

Prim's algorithm works locally on vertices. Start from any vertex and grow a single connected tree, repeatedly adding the cheapest edge that leaves the tree. A priority queue holds the candidate edges, or equivalently the vertices keyed by their cheapest connection to the tree.

The structure is strikingly close to Dijkstra's — the difference is what the key stores. Dijkstra keys on distance from the source, accumulating along the path; Prim keys on the weight of a single edge into the tree. That one change turns a shortest-path algorithm into a spanning-tree algorithm, and noticing it is a useful way to remember both.

With a binary heap Prim's is O((V + E) log V); with an adjacency matrix and a linear scan for the minimum it is O(V²), which is better on dense graphs.

The choice follows density. Kruskal for sparse graphs — its cost is driven by the edge count and the sort. Prim for dense graphs — the O(V²) form avoids the heap entirely when E approaches V². Kruskal also handles disconnected input naturally, producing a spanning forest without modification, whereas Prim finds only the component containing its start vertex.

Kruskal's against Prim's
	Kruskal's	Prim's
Grows	Many components merging	One connected tree
Order	All edges, sorted globally	Cheapest edge leaving the tree
Key structure	Union-find	Priority queue
Complexity	O(E log E)	O((V+E) log V), or O(V²) dense
Best for	Sparse graphs	Dense graphs
Disconnected input	Gives a forest naturally	Finds one component only

Kruskal sorts every edge and rejects cycles with union-find
Prim grows one tree, taking the cheapest edge that leaves it
Prim is Dijkstra with the key changed from path cost to edge weight
Sparse favours Kruskal; dense favours Prim's O(V²) form

Implementation

Kruskal and Prim build an MST

edges = sorted([(1, 0, 2), (1, 3, 4), (2, 1, 2), (3, 0, 1), (4, 2, 4)])
parent = list(range(5))

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

total = 0
for w, u, v in edges:
    a, b = find(u), find(v)
    if a != b:
        parent[a] = b
        total += w

print("MST weight:", total)

#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <functional>
#include <tuple>
#include <array>
#include <numeric>
using namespace std;
int main()
{
    vector<array<int,3>>e=
    {
        {
            1,0,2
        }
        ,
        {
            1,3,4
        }
        ,
        {
            2,1,2
        }
        ,
        {
            3,0,1
        }
        ,
        {
            4,2,4
        }
    };
    sort(e.begin(),e.end());
    vector<int>p=
    {
        0,1,2,3,4
    };
    function<int(int)>f=[&](int x)
    {
        return p[x]==x?x:p[x]=f(p[x]);
    };
    int s=0;
    for(auto a:e)
    {
        int u=f(a[1]),v=f(a[2]);
        if(u!=v)p[u]=v,s+=a[0];
    }
    cout<<"MST weight: "<<s;
}

import java.util.*;
class Main
{
    static int[]p=
    {
        0,1,2,3,4
    };
    static int f(int x)
    {
        return p[x]==x?x:(p[x]=f(p[x]));
    }
    public static void main(String[]z)
    {
        int[][]e=
        {
            {
                1,0,2
            }
            ,
            {
                1,3,4
            }
            ,
            {
                2,1,2
            }
            ,
            {
                3,0,1
            }
            ,
            {
                4,2,4
            }
        };
        Arrays.sort(e,(a,b)->a[0]-b[0]);
        int s=0;
        for(int[]a:e)
        {
            int u=f(a[1]),v=f(a[2]);
            if(u!=v)
            {
                p[u]=v;
                s+=a[0];
            }
        }
        System.out.print("MST weight: "+s);
    }
}

Watch it run

Step through it

Running on weighted graph A–E

Output

Read all 13 Steps

List weighted edges Read every undirected edge and its weight.
Sort edges Kruskal processes edges from lightest to heaviest.
Take A–C (1) A and C have different roots, so the lightest edge is safe.
Union A and C Union-find merges their components.
Take B–C (2) B and C are in different components; accept weight 2.
Union B with AC The forest now contains component ABC.
Inspect A–B (3) A and B already have a path through C.
Reject cycle edge Union-find finds the same root and rejects A–B; accepting it would create a cycle.
Take C–E (4) Connect E to component ABC with weight 4.
Take D–E (1) Connect D to E with weight 1.
All vertices connected Four accepted edges connect five vertices: the tree is complete.
Compare Prim's frontier Prim would choose the cheapest edge crossing its current cut and reaches the same total.
Finish Accepted weights 1+2+4+1 give total 8.

Edge Cases and Related Problems

Disconnected graphs. Kruskal's runs to completion and returns a spanning forest with fewer than V−1 edges — and counting the accepted edges is how you detect the situation: k components yield V−k edges. Prim's silently returns the MST of only its starting component, so it must be restarted from each unvisited vertex to produce a forest.

Verifying a claimed MST is a reasonable follow-up question. Check three things: it has exactly V−1 edges, it is connected and acyclic, and — the substantive test — no non-tree edge is lighter than the heaviest edge on the tree path between its endpoints. That last is the cycle property, the cut property's dual, and it is what makes the verification complete rather than superficial.

Ties in weight produce multiple valid MSTs. All have the same total, and any is a correct answer unless the problem specifies a tie-break. Notably, the multiset of edge weights is the same across every MST of a graph, even when the edge sets differ.

Negative weights are fine. Unlike Dijkstra, MST algorithms have no problem with them — the cut property makes no assumption about sign, and since a spanning tree must include V−1 edges regardless, there is no incentive to loop.

Maximum spanning tree is obtained by negating the weights, or by sorting descending in Kruskal's. Nothing else changes.

Two related problems worth distinguishing. A Steiner tree connects a specified subset of vertices, optionally using others as intermediates, and is NP-hard — the relaxation from 'all vertices' to 'these vertices' changes the problem's difficulty completely. And the second-best MST is found by trying each non-tree edge in turn, adding it, and removing the heaviest edge on the cycle it creates.

For very large graphs, Borůvka's algorithm — actually the oldest of the three, from 1926 — adds the cheapest edge out of every component simultaneously in each round, halving the component count per round. Its parallelism makes it the basis of distributed MST implementations.

k components means the forest has V−k edges — Kruskal reveals this
Verify with the cycle property, not just the edge count
Negative weights are harmless here, unlike in Dijkstra
Steiner tree — connecting only a subset — is NP-hard