Minimum Spanning Tree — Kruskal vs Prim, cut property

Một network engineer cần kết nối 100 datacenter bằng cáp quang. Mỗi cặp datacenter có chi phí lắp đặt khác nhau — distance, terrain, licensing. Mục tiêu: tìm tập cáp với tổng chi phí nhỏ nhất sao cho mọi datacenter đều được kết nối với nhau.

Thêm cáp thừa (tạo vòng lặp) là lãng phí — nếu datacenter A và B đã kết nối qua C, thêm cáp trực tiếp A–B chỉ tốn thêm tiền mà không tăng connectivity. Cấu hình tối ưu là một tree — connected, acyclic, đúng V-1 cạnh cho V đỉnh.

Bài này dạy 2 algorithm tìm Minimum Spanning Tree: Kruskal (sort edges và dùng Disjoint Set Union — preview lesson 09), Prim (grow tree với PriorityQueue), khi nào chọn cái nào, và cut property làm nền tảng correctness cho cả hai.

1. Analogy — Thiết kế đường dây điện

Có N ngôi nhà cần điện. Kỹ sư đo chi phí rải dây giữa từng cặp nhà — khoảng cách, địa hình, vật cản. Cần tìm cách rải dây với tổng chi phí nhỏ nhất sao cho mọi nhà đều có điện.

Nếu rải dây tạo vòng lặp — nhà A kết nối với B qua cả đường thẳng lẫn đường vòng qua C — thì đường vòng hoàn toàn thừa. Cấu hình tối ưu: N nhà, N-1 đường dây, không vòng lặp, mọi nhà kết nối. Đây chính xác là spanning tree.

2. Định nghĩa MST

Cho graph G = (V, E) connected, undirected, weighted:

• Spanning tree: tập con E' của E sao cho tất cả V vertex kết nối với nhau, đúng V-1 edges, không cycle.
• MST (Minimum Spanning Tree): spanning tree với tổng weight nhỏ nhất.

Số lượng MST:

• Nếu mọi edge weight khác nhau → MST là duy nhất.
• Nếu có tie (edge weight bằng nhau) → có thể tồn tại nhiều MST có cùng tổng weight tối thiểu.

Lưu ý quan trọng: MST tối ưu tổng weight toàn cây, không tối ưu từng shortest path riêng lẻ giữa các cặp vertex. Đây là điểm khác biệt cốt lõi so với Dijkstra.

3. Cut property — nền tảng correctness

Cut là cách chia tập vertex V thành 2 disjoint set: S và V-S (mọi vertex thuộc đúng một trong hai set).

Cut edge là edge có một endpoint trong S và một endpoint trong V-S — nghĩa là edge này "bắc cầu" qua cut.

Cut property: với bất kỳ cut (S, V-S) nào, edge có weight nhỏ nhất qua cut đó phải thuộc ít nhất một MST.

Tại sao? Gọi edge đó là e. Giả sử e không thuộc MST T. Thêm e vào T tạo ra đúng một cycle — cycle đó phải chứa ít nhất một edge f khác qua cut này (vì cycle phải thoát ra và quay vào S). Do e là edge nhỏ nhất qua cut: weight(e) <= weight(f). Thay f bằng e trong T cho spanning tree T' với tổng weight không tăng — mâu thuẫn với T là MST (hoặc T' cũng là MST nếu tie).

Ý nghĩa thực tế: cả Kruskal và Prim đều hoạt động bằng cách lặp lại cut property — tại mỗi bước, pick edge nhỏ nhất qua một cut nào đó, đảm bảo edge đó thuộc MST.

4. Kruskal algorithm

4.1 Ý tưởng

Kruskal xây MST theo góc nhìn edge-centric:

1. Sort tất cả edge theo weight ascending.
2. Iterate qua từng edge (từ nhỏ đến lớn): thêm edge vào MST nếu hai endpoint chưa nằm trong cùng một component (tức là thêm edge này không tạo cycle).
3. Dừng khi đã có V-1 edges.

Bước 2 — "hai endpoint có trong cùng component không?" — được giải bằng Disjoint Set Union (DSU). DSU sẽ được phân tích chi tiết ở lesson 09; ở đây dùng như black box với hai operation: find(x) trả root của component chứa x, union(x, y) gộp hai component.

4.2 Code Java

public class Kruskal {
    record Edge(int u, int v, int weight) {}

    public static List<Edge> mst(int n, List<Edge> edges) {
        // Sort all edges by weight ascending
        edges.sort(Comparator.comparingInt(Edge::weight));
        DisjointSet dsu = new DisjointSet(n);
        List<Edge> result = new ArrayList<>();

        for (Edge e : edges) {
            // Only add edge if it connects two different components (no cycle)
            if (dsu.union(e.u(), e.v())) {
                result.add(e);
                if (result.size() == n - 1) break; // MST complete
            }
        }
        return result; // result.size() < n-1 means graph is disconnected
    }

    static class DisjointSet {
        int[] parent;
        int[] rank;

        DisjointSet(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) parent[i] = i;
        }

        // Find root with path compression
        int find(int x) {
            if (parent[x] != x) parent[x] = find(parent[x]);
            return parent[x];
        }

        // Union by rank -- returns true if merged, false if already same component
        boolean union(int x, int y) {
            int rx = find(x), ry = find(y);
            if (rx == ry) return false; // same component -- adding would create cycle
            if (rank[rx] < rank[ry]) { int tmp = rx; rx = ry; ry = tmp; }
            parent[ry] = rx;
            if (rank[rx] == rank[ry]) rank[rx]++;
            return true;
        }
    }
}

4.3 Complexity

• Time: O(E log E) để sort + O(E × α(V)) cho DSU operations ≈ O(E log V). Hàm α là inverse Ackermann — tăng cực kỳ chậm, thực tế coi như hằng số.
• Space: O(V) cho DSU, O(E) để lưu edges.

4.4 Trace ví dụ

Graph 4 vertex, 5 edges:

0 ---(1)--- 1
|  \        |
(4) (3)    (2)
|     \     |
3 ---(5)--- 2

Edges sorted: (0,1,1), (1,2,2), (0,2,3), (0,3,4), (2,3,5).

V-1 = 3 edges đã có. Dừng. Tổng weight = 1+2+4 = 7.

5. Prim algorithm

5.1 Ý tưởng

Prim xây MST theo góc nhìn vertex-centric:

1. Bắt đầu từ một vertex bất kỳ (vertex 0).
2. Maintain PriorityQueue chứa các edge từ "tree-set" (các vertex đã thuộc MST) ra "non-tree" (các vertex chưa thuộc MST).
3. Lặp: poll edge nhỏ nhất từ PQ; nếu endpoint đích chưa trong tree — thêm vertex đó vào tree, thêm edge vào MST, đẩy tất cả edge từ vertex mới ra các neighbor chưa trong tree vào PQ.
4. Dừng khi tất cả vertex trong tree.

Đây là cut property applied trực tiếp: tại mỗi bước, cut là (tree-set, V - tree-set), và Prim luôn pick edge nhỏ nhất qua cut đó.

5.2 Code Java

public class Prim {
    record Edge(int from, int to, int weight) {}

    public static List<Edge> mst(int n, List<List<Edge>> adj) {
        boolean[] inTree = new boolean[n];
        // Min-heap by edge weight
        PriorityQueue<Edge> pq = new PriorityQueue<>(
            Comparator.comparingInt(Edge::weight)
        );
        List<Edge> result = new ArrayList<>();

        // Start from vertex 0
        inTree[0] = true;
        for (Edge e : adj.get(0)) pq.offer(e);

        while (!pq.isEmpty() && result.size() < n - 1) {
            Edge e = pq.poll();
            if (inTree[e.to()]) continue; // endpoint already in tree -- skip (lazy delete)

            // Add this vertex to the tree
            inTree[e.to()] = true;
            result.add(e);

            // Offer edges from new vertex to non-tree neighbors
            for (Edge next : adj.get(e.to())) {
                if (!inTree[next.to()]) pq.offer(next);
            }
        }
        return result;
    }
}

5.3 Complexity

• Time: O((V + E) log V) với binary heap. Mỗi trong V vertex được thêm vào tree một lần; mỗi trong E edge có thể được push vào PQ một lần (O(log E) = O(log V) per push).
• Space: O(V) cho inTree, O(E) worst-case cho PQ (lazy deletion).

5.4 Trace ví dụ

Cùng graph 4 vertex 5 edges như trên.

MST: 4, tổng weight = 7. Kết quả giống Kruskal.

6. Kruskal vs Prim — khi nào chọn gì

Khi nào Kruskal thắng Prim?

Với sparse graph (E nhỏ hơn nhiều so với V²), O(E log V) của Kruskal tốt hơn O((V+E) log V) của Prim. Ví dụ: V = 1000, E = 2000 (sparse). Kruskal ≈ 2000 × 10 = 20.000 operations chủ yếu. Prim ≈ (1000 + 2000) × 10 = 30.000 — chậm hơn một chút, nhưng không đáng kể ở scale này.

Khi nào Prim thắng Kruskal?

Dense graph (E gần V²). Với E = V², Kruskal sort E edges = V² log V operations. Prim vẫn O((V + V²) log V) ≈ O(V² log V) — tương đương. Nhưng Prim có thể được optimize thêm bằng adjacency matrix thay PQ, đạt O(V²) cho dense graph — thắng Kruskal rõ ràng.

7. Pitfall tổng hợp

Pitfall 1 — Kruskal trên disconnected graph trả spanning forest, không phải spanning tree:

// Graph has 2 components: {0,1,2} and {3,4}
// Kruskal will return edges connecting each component separately
List<Edge> result = Kruskal.mst(5, edges);
// result.size() = 3, not 4 (n-1)
// This is a minimum spanning FOREST -- correct for disconnected input,
// but caller must check result.size() == n-1 to detect disconnected graph
if (result.size() < n - 1) {
    throw new IllegalArgumentException("Graph is not connected");
}

Prim bắt đầu từ vertex 0 và chỉ xử lý component chứa vertex 0 — các component khác hoàn toàn bị bỏ qua.

Pitfall 2 — Prim PQ chứa duplicate entries:

// Multiple edges may reach the same vertex -- all get pushed to PQ
// When we expand vertex u, edges (u->v1), (u->v2) are pushed
// If v1 was already reachable from earlier, PQ has duplicate entries for v1
// CORRECT pattern: check inTree[e.to()] when POLLING, not when pushing
Edge e = pq.poll();
if (inTree[e.to()]) continue; // lazy delete -- safe to skip

Đây là cùng pattern "lazy deletion" như Dijkstra (lesson 05). Push nhiều entries vào PQ là bình thường và an toàn — chỉ cần kiểm tra khi poll. PQ có thể chứa tới O(E) entries — không ảnh hưởng correctness, chỉ tốn thêm space.

Pitfall 3 — Nhầm MST với shortest path tree (Dijkstra):

// MST: minimize TOTAL weight of the tree
// Shortest path tree: minimize distance from source to EACH vertex individually
//
// Counter-example (4 vertices):
// Edges: 0->1 w1, 0->2 w3, 1->3 w1, 2->3 w1
//
// MST: {(0,1,1), (1,3,1), (2,3,1)} -- total weight 3
//   (connects 0-1-3-2, total cost 3)
//
// Dijkstra shortest path tree from vertex 0:
//   dist[0]=0, dist[1]=1, dist[2]=3, dist[3]=2
//   Tree edges: {(0,1,1), (1,3,1), (0,2,3)} -- total weight 5
//   Path 0->2 goes directly (cost 3), not via 3->2 (cost 1+1+1=3, same but different tree)
//
// Key: MST edge (2,3,1) means "connect vertex 2 cheapest to the tree overall"
//      Dijkstra edge (0,2,3) means "reach vertex 2 from source 0 with minimum cost"
//      These are DIFFERENT objectives.

Đừng dùng Dijkstra để tìm MST — chúng giải hai bài toán khác nhau.

8. Variants và mở rộng

Borůvka's algorithm (1926): thuật toán MST đầu tiên được phát minh, trước cả Kruskal và Prim. Mỗi vòng lặp: mỗi component tìm edge nhỏ nhất ra ngoài component đó và thêm tất cả cùng lúc. Số component giảm xuống một nửa sau mỗi vòng → O(E log V) total. Đặc biệt phù hợp cho distributed MST — mỗi component có thể tìm min edge song song, không cần coordinator trung tâm.

Kruskal với lazy sort: thay vì sort toàn bộ edge list một lần, dùng min-heap để lấy edge nhỏ nhất theo từng bước. Useful khi chỉ cần một phần MST hoặc khi edge list quá lớn để sort toàn bộ cùng lúc.

MST verification: cho trước một spanning tree T, kiểm tra T có phải MST của G không trong O(V+E) — không cần chạy Kruskal/Prim lại. Dùng kỹ thuật cycle property: với mỗi non-tree edge e, nếu weight(e) nhỏ hơn max weight trên path trong T giữa hai endpoint của e, thì T không phải MST. Linear verification algorithm của Dixon, Rauch, Tarjan (1992).

9. Ứng dụng thực tế

Network design — telco và datacenter: bài toán gốc của MST. Thiết kế mạng lưới cáp quang kết nối N điểm với chi phí tổng thể nhỏ nhất. Amazon AWS dùng MST-based algorithm để lên kế hoạch đặt cáp giữa các availability zone. Điều kiện thực tế phức tạp hơn (reliability, redundancy) — MST là baseline, sau đó thêm constraints.

Cluster analysis trong machine learning: hierarchical clustering với single-link method tương đương xây MST trên distance graph, rồi cắt bỏ các edge có weight lớn nhất. Số cluster = số cut. Scikit-learn AgglomerativeClustering(linkage='single') dùng MST internally cho large datasets.

Image segmentation trong computer vision: treat mỗi pixel là vertex, edge weight là difference giữa hai pixel liền kề. MST trên pixel graph xác định vùng ảnh liên kết theo màu/độ sáng. Felzenszwalb-Huttenlocher algorithm (2004) dùng MST variant để segment ảnh thời gian thực.

Approximation cho Traveling Salesman Problem: MST là lower bound cho TSP — bất kỳ TSP tour nào cũng có weight ít nhất bằng MST weight. Doubled MST (đi cạnh MST 2 lần) cho upper bound TSP × 2. Christofides algorithm (1976): MST + minimum weight perfect matching trên odd-degree vertices → tour với weight tối đa 1.5 × optimal TSP. Đây là approximation ratio tốt nhất đã biết cho general metric TSP trong nhiều thập kỷ.

10. Deep Dive

11. Tóm tắt

• MST là spanning tree (kết nối mọi vertex, V-1 edges, không cycle) với tổng edge weight nhỏ nhất. Unique nếu mọi weight khác nhau.
• Cut property: với bất kỳ cut (S, V-S) nào, edge nhỏ nhất qua cut phải thuộc ít nhất một MST — đây là nền tảng correctness cho cả Kruskal và Prim.
• Kruskal: sort tất cả edges tăng dần, thêm edge nếu không tạo cycle (dùng DSU), O(E log V). Tốt cho sparse graph và edge-list input.
• Prim: grow tree từ một vertex, PQ chứa edges ra ngoài tree, luôn pick edge nhỏ nhất, O((V+E) log V). Tốt cho dense graph và adjacency-list input.
• Lazy deletion trong Prim: push edge nhiều lần vào PQ an toàn — kiểm tra inTree[e.to()] khi poll, không khi push. Tương tự pattern Dijkstra.
• Disconnected graph: Kruskal trả minimum spanning forest (result.size() nhỏ hơn V-1); Prim chỉ xử lý component của vertex 0.
• MST khác shortest path tree: MST tối ưu tổng weight toàn cây; Dijkstra tối ưu khoảng cách từ source đến từng vertex riêng lẻ — hai mục tiêu khác nhau.
• Ứng dụng: network design, ML clustering, image segmentation, TSP approximation (Christofides 1.5×).

12. Tự kiểm tra

Bài tiếp theo: Disjoint Set Union — path compression, union by rank