DSU, MST, and offline activation · HTML
For G=(V,E) with comparable weights, find a spanning tree T of |V|-1 edges minimizing their total weight.
Recognition signals
- Connect every vertex at minimum total construction cost
- Edges may be chosen freely from candidates
- Undirected edges have sortable costs
- An edge decision only needs cross-component status
- Savings or bottleneck connectivity may also be requested
False friends
| Signal | Why it is different |
|---|
| Single-source shortest paths | An MST minimizes the tree's total weight, not the path from one source to each vertex. |
| Directed minimum connection | Ordinary Kruskal is for undirected graphs; directed spanning structures need different machinery. |
Core invariant
After each scanned weight, the chosen forest can be extended to some MST; accept only the lightest edge crossing two current components.
State, transition, and processing order
| Item | Definition |
|---|
| State | Sorted edges, a DSU for the forest, accumulated total, and chosen edges. |
| Transition | Read edges in nondecreasing weight; accept and add the weight when union succeeds, otherwise reject the cycle-forming edge. |
| Frontier / order | Unscanned edges form a weight-ordered frontier; the lightest cross-component edge is safe by the cut property. |
Python skeleton
def kruskal(n, edges):
p, sz = list(range(n)), [1] * n
def find(x):
while x != p[x]:
p[x] = p[p[x]]; x = p[x]
return x
def union(a, b):
a, b = find(a), find(b)
if a == b: return False
if sz[a] < sz[b]: a, b = b, a
p[b] = a; sz[a] += sz[b]
return True
total, chosen = 0, []
for w, u, v in sorted(edges):
if union(u, v):
total += w; chosen.append((u, v, w))
if len(chosen) == n - 1: break
return (total, chosen) if len(chosen) == n - 1 else None
Correctness sketch
- The cut property places a lightest edge across any current cut in some MST.
- Weight order makes an accepted edge no heavier than any unprocessed replacement.
- DSU rejects intra-component edges, so the chosen set stays acyclic.
- In a connected graph, n-1 consecutive safe choices form an MST.
Complexity
| Time | Space | Parameters |
|---|
| O(E log E), dominated by sorting | O(V+E) | V vertices and E edges; DSU work is O(E α(V)) |
Edge cases
- A disconnected graph has no full MST
- Parallel edges compete normally
- Self-loops are always rejected
- Negative weights are valid
- One vertex has an empty tree of weight zero
Error patterns
| Pattern | Why it fails / fix |
|---|
| Sorting the wrong tuple field | For (u,v,w), provide an explicit weight key or store (w,u,v). |
| Scanning after V-1 choices | The tree is already complete; stop early. |
| Skipping the connectivity check | Fewer than V-1 choices yield only a forest, not a spanning tree. |
Selection and exclusion rules
- An edge list is native input: Kruskal is usually direct.
- A dense adjacency matrix may favor Prim.
- A source-to-target objective is shortest path, not MST.
- Threshold connectivity queries suggest offline activation with the same sorting skeleton.
Original micro-example
| Part | Detail |
|---|
| Result | Choosing 1, 2, and 3 connects all stations for total 6. |
| Scenario | Four stations have candidate edge weights 2, 1, 3, 8, and 5. |
| Walkthrough | The first three safe edges complete the tree, so expensive edges need not be scanned. |
Recall prompts
My notes