Minimum Spanning Tree — Kruskal vs Prim, cut property

TL;DR: Minimum Spanning Tree (MST) là spanning tree (kết nối mọi vertex, V-1 cạnh, không cycle) với tổng edge weight nhỏ nhất. Hai thuật toán kinh điển: Kruskal — sort toàn bộ cạnh tăng dần, thêm từng cạnh nếu không tạo cycle (dùng DSU để kiểm tra), O(E log V); Prim — grow tree từ một vertex, MinHeap chứa các cạnh ra ngoài tree, luôn pick cạnh nhỏ nhất, O((V+E) log V). Cả hai đều dựa trên cùng một nền tảng lý thuyết: cut property — edge nhỏ nhất qua bất kỳ cut (S, V-S) nào phải thuộc ít nhất một MST.

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 MinHeap), 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 Pseudocode

Kruskal(G, V, E):
    -- Sắp xếp tất cả cạnh theo trọng số tăng dần
    sắp xếp E theo weight tăng dần

    DSU dsu <- khởi tạo với V đỉnh    -- mỗi đỉnh là component riêng
    result <- []

    for each cạnh (u, v, w) trong E (theo thứ tự đã sắp xếp):
        -- Chỉ thêm nếu u và v thuộc component khác nhau (không tạo cycle)
        if dsu.union(u, v) = true:
            result.append((u, v, w))
            if result.length = V - 1:
                break    -- MST đã đủ V-1 cạnh

    return result    -- nếu result.length < V-1: graph không liên thông

Time: O(E log E) để sort + O(E × α(V)) cho DSU ≈ O(E log V) Space: O(V)

α là inverse Ackermann — tăng cực kỳ chậm, thực tế coi như hằng số.

4.3 Trace ví dụ — graph 4 vertex

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 cạnh đã 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 MinHeap 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: lấy edge nhỏ nhất từ heap; 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 heap.
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 Pseudocode

Prim(G, n):
    inTree[0..n-1] <- false
    H <- MinHeap rỗng    -- keyed by edge weight
    result <- []

    -- Bắt đầu từ đỉnh 0
    inTree[0] <- true
    for each cạnh (0, v, w) kề đỉnh 0:
        H.push((0, v, w))

    while H không rỗng và result.length < n - 1:
        (u, v, w) <- H.pop()    -- lấy cạnh có trọng số nhỏ nhất
        if inTree[v]:
            continue             -- v đã trong tree, bỏ qua (lazy delete)

        -- Thêm v vào tree
        inTree[v] <- true
        result.append((u, v, w))

        -- Đẩy các cạnh từ v ra neighbor chưa trong tree
        for each cạnh (v, x, wx) kề v:
            if not inTree[x]:
                H.push((v, x, wx))

    return result

Time: O((V+E) log V) Space: O(V+E)

5.3 Trace ví dụ — cùng graph 4 vertex

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

graph LR
    subgraph "Kruskal — thêm cạnh nhỏ nhất không tạo cycle"
        K0((0)) -- "w=1" --- K1((1))
        K1 -- "w=2" --- K2((2))
        K0 -- "w=4" --- K3((3))
    end
    subgraph "Prim — grow tree từ đỉnh 0"
        P0((0)) -- "w=1" --- P1((1))
        P1 -- "w=2" --- P2((2))
        P0 -- "w=4" --- P3((3))
    end

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 heap, đạ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 có 2 component: {0,1,2} và {3,4}
-- Kruskal trả cạnh kết nối mỗi component riêng biệt
-- result.length = 3, không phải 4 (V-1)
-- Đây là minimum spanning FOREST -- đúng cho disconnected input
-- Nhưng caller phải kiểm tra result.length = n-1 để phát hiện graph không liên thông

if result.length < n - 1:
    báo lỗi "Graph không liên thông"

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 heap chứa duplicate entries

-- Nhiều cạnh có thể dẫn đến cùng một vertex v -- tất cả được push vào heap
-- Khi poll entry (u->v, w): kiểm tra inTree[v] khi POLL, không khi PUSH
(u, v, w) <- H.pop()
if inTree[v]: continue    -- lazy delete -- an toàn để bỏ qua

Đây là cùng pattern "lazy deletion" như Dijkstra (lesson 05). Push nhiều entries vào heap là bình thường và an toàn — chỉ cần kiểm tra khi poll. Heap 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: tối ưu TỔNG weight của cây
-- Shortest path tree: tối ưu khoảng cách từ source đến TỪNG vertex riêng lẻ
--
-- Ví dụ đối chiếu (4 đỉnh):
-- Cạnh: 0->1 w1, 0->2 w3, 1->3 w1, 2->3 w1
--
-- MST: {(0,1,1), (1,3,1), (2,3,1)} -- tổng weight = 3
-- Dijkstra shortest path tree từ vertex 0:
--   dist[0]=0, dist[1]=1, dist[2]=3, dist[3]=2
--   Cạnh tree: {(0,1,1), (1,3,1), (0,2,3)} -- tổng weight = 5
--
-- Điểm mấu chốt: MST cạnh (2,3,1) = "kết nối vertex 2 vào cây rẻ nhất"
--               Dijkstra cạnh (0,2,3) = "đến vertex 2 từ nguồn 0 với chi phí nhỏ nhất"
--               Hai mục tiêu KHÁC NHAU

Khô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 của 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ỷ — cho đến 2020, khi Karlin–Klein–Oveis Gharan công bố thuật toán phá ngưỡng 1.5 (đạt 1.5 − ε với ε rất nhỏ).

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, MinHeap 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 heap an toàn — kiểm tra inTree[v] khi poll, không khi push. Tương tự pattern Dijkstra.
• Disconnected graph: Kruskal trả minimum spanning forest (result.length 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