Minimum Spanning Trees

Spanning tree, cut property, cycle property, minimum spanning forest for disconnected graphs.

Concepts

Spanning tree, cut property, cycle property, minimum spanning forest for disconnected graphs.

Cut property: for any division of the vertices into two groups, the lightest edge crossing between them belongs to some MST.

Cycle property: the heaviest edge on any cycle is not needed (some MST excludes it).

Algorithms

Kruskal + DSU.

Prim + priority queue.

Borůvka overview.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

#include <bits/stdc++.h>
using namespace std;

struct DSU { vector<int> p; explicit DSU(int n) : p(n) { iota(p.begin(), p.end(), 0); } int f(int x) { return p[x] == x ? x : p[x] = f(p[x]); } bool u(int a, int b) { a = f(a); b = f(b); if (a == b) return false; p[a] = b; return true; } };

long long kruskal(int V, vector<tuple<int, int, int>> e, vector<tuple<int, int, int>>* chosen = nullptr) {
    sort(e.begin(), e.end(), [](auto& a, auto& b) { return get<2>(a) < get<2>(b); });
    DSU d(V); long long total = 0;
    for (auto [u, v, w] : e) if (d.u(u, v)) { total += w; if (chosen) chosen->push_back({u, v, w}); }   // skip edges that close a cycle
    return total;
}
long long prim(int V, const vector<tuple<int, int, int>>& e) {
    vector<vector<pair<int, int>>> adj(V);
    for (auto [u, v, w] : e) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); }
    vector<bool> in(V, false); long long total = 0;
    using T = pair<int, int>;
    for (int s = 0; s < V; ++s) {                          // restart per component: minimum spanning forest
        if (in[s]) continue;
        priority_queue<T, vector<T>, greater<T>> pq; pq.push({0, s});
        while (!pq.empty()) {
            aut
…

Kruskal MST weight: 37, edges: 6-7(1) 2-8(2) 5-6(2) 0-1(4) 2-5(4) 2-3(7) 0-7(8) 3-4(9)
Prim MST weight: 37
Kruskal and Prim agree on 300 random (possibly disconnected) graphs

Complexity

Explain sorting/heap costs in terms of V and E, and compare sparse versus dense graph implementations.

O(E log E) (sorting dominates; DSU is near-constant) simple; natural for edge lists Prim, binary heap grows one tree; natural for adjacency lists Prim, array (no heap) best for dense graphs where E ≈ V² each round, every component adds its lightest outgoing edge; parallelises well

Both programs above compute a minimum spanning forest when the graph is disconnected: Kruskal naturally, Prim by restarting from each unvisited vertex.

Quiz

? Kruskal skips an edge when…
+ its endpoints are already in the same DSU component — it would close a cycle :: Cycle property.
- its weight is odd :: No.
- it is the heaviest edge overall :: Not necessarily.
- the tree has V edges :: A spanning tree has V − 1 edges.

? For a dense graph with E ≈ V², which Prim implementation is asymptotically best?
+ The O(V²) array version :: E log V would be V² log V.
- Binary heap :: O(E log V) = O(V² log V).
- Kruskal :: O(E log E).
- BFS :: Not an MST algorithm.

? Which statements are true? (select all that apply)
+ If all edge weights are distinct, the MST is unique :: Standard result.
+ The lightest edge in the graph is in some MST :: Cut property.
- An MST gives shortest paths between all pairs :: It does not.
+ Disconnected graphs have a minimum spanning forest :: One tree per component.