<style> .reveal-up, .reveal-left, .reveal-right, .reveal-stagger > * { opacity: 1 !important; transform: none !important; } </style>
  1. Learn
  2. DSA
  3. Graphs
All lessons in this course

Foundations

Linear data structures

Searching and sorting

Hashing and problem-solving techniques

Trees

Graphs

Algorithm design

Master level

Lesson 37 of 50 14 minAdvanced

Minimum spanning trees

Connect every vertex with the least total edge weight: what a spanning tree is, Kruskal’s and Prim’s algorithms, why greedy works here, and how an MST differs from shortest paths.

The site needs temporary power to all seven places, and cable can only run along the roads. Which roads should carry cable so that every place is connected, using the least total cable? This is the minimum spanning tree (MST) problem. The same question appears for pipe networks, fibre and road building, and in clustering data.

Spanning trees

A spanning tree of a connected graph uses some of its edges to connect all V vertices with no cycles. It always has exactly V − 1 edges: fewer cannot connect everything, and one more would close a loop. A graph has many spanning trees; the minimum one has the smallest total weight.

Interactive

Minimum spanning tree

Connect all seven places with the least total length of temporary road (weights). Any set of roads that connects everything without loops is a spanning tree; we want the cheapest.

42365234716ABCDEFG
Roads, cheapest first
F-G 1C-E 2A-D 2C-F 3B-E 3E-G 4A-B 4D-E 5E-F 6B-C 6D-G 7
Roads 0 / 6 · Total 0
Kruskal: sort all roads from cheapest to most expensive. Take each one unless it would close a loop.

Kruskal: cheapest edges first

Sort all edges by weight. Go through them from cheapest to most expensive and take each edge unless both ends are already connected (it would close a loop). Stop after V − 1 edges. To check “already connected?” quickly, Kruskal uses a union-find structure (explained in full in the next lesson; here it is a few lines).

Kruskal.cs
string names = "ABCDEFG";var roads = new List<(char A, char B, int W)>{    ('E', 'G', 4), ('C', 'E', 2), ('C', 'F', 3), ('A', 'B', 4), ('A', 'D', 2), ('B', 'E', 3),    ('B', 'C', 6), ('D', 'E', 5), ('D', 'G', 7), ('F', 'G', 1), ('E', 'F', 6)}; var parent = Enumerable.Range(0, names.Length).ToArray();int Find(int x) => parent[x] == x ? x : parent[x] = Find(parent[x]); int total = 0;var chosen = new List<string>();foreach (var (a, b, w) in roads.OrderBy(r => r.W))  // stable: equal weights keep list order{    int ra = Find(names.IndexOf(a)), rb = Find(names.IndexOf(b));    if (ra == rb)                                 // already connected: would make a loop    {        Console.WriteLine($"Skip {a}{b}({w}): {a} and {b} are already connected");        continue;    }    parent[ra] = rb;                              // merge the two groups    chosen.Add($"{a}{b}({w})");    total += w;    if (chosen.Count == names.Length - 1) break;  // V − 1 edges: done}Console.WriteLine(string.Join(" ", chosen));Console.WriteLine($"Total: {total}");
Output
Skip EG(4): E and G are already connected
FG(1) CE(2) AD(2) CF(3) BE(3) AB(4)
Total: 15

E–G costs 4, the same as A–B, but by then E and G are already joined through E–C–F–G, so taking it would close a loop. Sorting dominates the running time: O(E log E). The union-find checks are almost O(1) each.

Prim: grow one tree

Start from any vertex. Repeatedly add the cheapest edge that leaves the tree (one end inside, one outside). A priority queue holds the candidate edges, just like Dijkstra, except the priority is the edge weight alone, not the distance from the start.

Prim.cs
var graph = new Dictionary<char, List<(char To, int W)>>();void Road(char a, char b, int w){    if (!graph.ContainsKey(a)) graph[a] = new();    if (!graph.ContainsKey(b)) graph[b] = new();    graph[a].Add((b, w));    graph[b].Add((a, w));}Road('A', 'B', 4); Road('A', 'D', 2); Road('B', 'E', 3); Road('B', 'C', 6);Road('D', 'E', 5); Road('C', 'E', 2); Road('C', 'F', 3); Road('E', 'G', 4);Road('D', 'G', 7); Road('F', 'G', 1); Road('E', 'F', 6); var inTree = new HashSet<char>();var pq = new PriorityQueue<(char From, char To), int>();pq.Enqueue(('A', 'A'), 0);                       // start at Aint total = 0;var added = new List<string>();while (pq.TryDequeue(out var edge, out int w)){    if (!inTree.Add(edge.To)) continue;           // already in the tree: skip    total += w;    if (edge.From != edge.To) added.Add($"{edge.From}{edge.To}({w})");    foreach (var (next, nw) in graph[edge.To])        if (!inTree.Contains(next)) pq.Enqueue((edge.To, next), nw);}Console.WriteLine(string.Join(" ", added));Console.WriteLine($"Total: {total}");
Output
AD(2) AB(4) BE(3) EC(2) CF(3) FG(1)
Total: 15

O(E log V) with a heap. Both algorithms give a minimum total; if several edges share a weight, they may pick different (equally cheap) trees.

Why does greedy work here?

The cut property: split the vertices into any two groups. The cheapest edge crossing between the groups belongs to some minimum spanning tree. If an MST did not use it, you could add it (making a loop that crosses the split twice), remove the more expensive crossing edge on that loop, and get a cheaper or equal tree. Both Kruskal and Prim only ever take such a cheapest crossing edge.

Quick check

A connected graph has 50 vertices and 300 edges. How many edges does its minimum spanning tree have?

Quick check

Kruskal looks at an edge whose two ends are already in the same group. What does it do?

Practice

Points on a site plan must all be connected by cable trenches; a trench between two points costs their Manhattan distance |x₁ − x₂| + |y₁ − y₂|. Every pair can be connected. Find the minimum total cost for points (0,0), (2,2), (3,10), (5,2), (7,0). Expected: 20. Since the graph is complete (dense), use the simple O(V²) version of Prim with an array instead of a heap.

Show a hint

Keep best[i] = cheapest known connection from point i to the tree. Repeat V times: pick the unused point with the smallest best[i], add it, then update best[] for the others using distances from the new point.

Show the solution
Solution.cs
int[][] pts = { new[] { 0, 0 }, new[] { 2, 2 }, new[] { 3, 10 }, new[] { 5, 2 }, new[] { 7, 0 } };Console.WriteLine(MinTrenchCost(pts)); static int MinTrenchCost(int[][] p){    int n = p.Length, total = 0;    var best = new int[n];    var used = new bool[n];    Array.Fill(best, int.MaxValue);    best[0] = 0;    for (int step = 0; step < n; step++)    {        int u = -1;        for (int i = 0; i < n; i++)            if (!used[i] && (u == -1 || best[i] < best[u])) u = i;        used[u] = true;        total += best[u];        for (int v = 0; v < n; v++)        {            int cost = Math.Abs(p[u][0] - p[v][0]) + Math.Abs(p[u][1] - p[v][1]);            if (!used[v] && cost < best[v]) best[v] = cost;        }    }    return total;}
Output
20

Remember

  • A spanning tree connects all V vertices with V − 1 edges and no cycles; the MST has the least total weight.
  • Kruskal: sort edges, take each one that joins two different groups (union-find): O(E log E).
  • Prim: grow one tree, always adding the cheapest edge leaving it: O(E log V).
  • Greedy works because of the cut property. An MST does not give shortest paths.
0 of 50 lessons completed