PENALGO

Giao diện

Minimum Spanning Tree — Cây khung nhỏ nhất ​

Bạn là kỹ sư hạ tầng mạng, được giao nhiệm vụ kéo cáp quang nối 20 thành phố. Mỗi tuyến cáp có chi phí khác nhau phụ thuộc địa hình. Yêu cầu: mọi thành phố phải liên thông, tổng chi phí thấp nhất. Bạn không cần nối trực tiếp mọi cặp — chỉ cần đủ cạnh để tất cả liên thông. Đó chính xác là bài toán Minimum Spanning Tree (MST).

MST xuất hiện khắp nơi: thiết kế mạng máy tính, phân cụm dữ liệu (clustering), xấp xỉ TSP, và thậm chí cả phân tích hình ảnh. Hai thuật toán kinh điển — Kruskal (greedy trên cạnh + DSU) và Prim (greedy trên đỉnh + priority queue) — mỗi cái mạnh ở một context khác nhau.

Bức tranh tư duy ​

Hình dung bạn cần nối N hòn đảo bằng cầu. Mỗi cầu có chi phí xây khác nhau. Bạn muốn mọi đảo liên thông với tổng chi phí cầu thấp nhất.

text
Đảo A ---4--- Đảo B ---8--- Đảo C
  |  \          |           /
  2    3        7         5
  |      \      |       /
Đảo D ---6--- Đảo E ---1--- Đảo F

MST (tổng = 2 + 3 + 1 + 5 + 4 = 15):
A--D (2), A--B (hoặc A--E) (3), E--F (1), F--C (5), A--B (4)

Hai cách tiếp cận:

  • Kruskal: xếp tất cả cầu theo chi phí tăng dần. Duyệt từng cầu — nếu nối hai đảo chưa liên thông, xây nó. Bỏ qua nếu tạo vòng.
  • Prim: bắt đầu từ một đảo, liên tục xây cầu rẻ nhất ra đảo mới chưa thăm.

📌 Cut Property — nền tảng lý thuyết

Với mọi cách chia đồ thị thành hai nhóm (cut), cạnh có trọng số nhỏ nhất qua cut chắc chắn thuộc MST. Cả Kruskal và Prim đều dựa trên tính chất này.

Cốt lõi kỹ thuật ​

Kruskal's Algorithm — Sort edges + DSU ​

Sắp xếp tất cả cạnh theo trọng số. Duyệt từng cạnh: nếu hai đỉnh chưa cùng component (dùng DSU), thêm cạnh vào MST. Dừng khi có V-1 cạnh.

cpp
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;

struct Edge { int u, v, w; };

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

pair<long long, vector<Edge>> kruskal(int V, vector<Edge>& edges) {
    sort(edges.begin(), edges.end(),
         [](auto& a, auto& b) { return a.w < b.w; });

    DSU dsu(V);
    vector<Edge> mst;
    long long total = 0;

    for (auto& e : edges) {
        if (dsu.unite(e.u, e.v)) {
            mst.push_back(e);
            total += e.w;
            if ((int)mst.size() == V - 1) break;
        }
    }
    return {total, mst};
}
python
def kruskal(V: int, edges: list[tuple[int, int, int]]) -> tuple[int, list]:
    edges.sort(key=lambda e: e[2])
    dsu = DSU(V)
    mst = []
    total = 0

    for u, v, w in edges:
        if dsu.unite(u, v):
            mst.append((u, v, w))
            total += w
            if len(mst) == V - 1:
                break

    return total, mst
java
import java.util.*;

class Kruskal {
    static long[] solve(int V, int[][] edges) {
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);
        DSU dsu = new DSU(V);
        long total = 0;
        int count = 0;

        for (int[] e : edges) {
            if (dsu.unite(e[0], e[1])) {
                total += e[2];
                if (++count == V - 1) break;
            }
        }
        return new long[]{total, count};
    }
}
go
import "sort"

type Edge struct{ U, V, W int }

func kruskal(V int, edges []Edge) (int, []Edge) {
    sort.Slice(edges, func(i, j int) bool {
        return edges[i].W < edges[j].W
    })

    dsu := NewDSU(V)
    mst := []Edge{}
    total := 0

    for _, e := range edges {
        if dsu.Unite(e.U, e.V) {
            mst = append(mst, e)
            total += e.W
            if len(mst) == V-1 { break }
        }
    }
    return total, mst
}

Prim's Algorithm — Priority queue greedy ​

Bắt đầu từ đỉnh bất kỳ. Duy trì priority queue (min-heap) chứa các cạnh ra ngoài tập đã thăm. Mỗi bước, lấy cạnh rẻ nhất nối đến đỉnh chưa thăm, thêm vào MST. Tương tự Dijkstra, nhưng key là trọng số cạnh thay vì khoảng cách tích lũy.

cpp
#include <vector>
#include <queue>
using namespace std;

long long prim(int V, vector<vector<pair<int,int>>>& adj) {
    vector<bool> inMST(V, false);
    // {weight, vertex}
    priority_queue<pair<int,int>, vector<pair<int,int>>,
                   greater<>> pq;
    pq.push({0, 0});
    long long total = 0;
    int count = 0;

    while (!pq.empty() && count < V) {
        auto [w, u] = pq.top(); pq.pop();
        if (inMST[u]) continue;
        inMST[u] = true;
        total += w;
        count++;
        for (auto [v, wt] : adj[u]) {
            if (!inMST[v]) pq.push({wt, v});
        }
    }
    return total;
}
python
import heapq

def prim(V: int, adj: list[list[tuple[int, int]]]) -> int:
    in_mst = [False] * V
    pq = [(0, 0)]  # (weight, vertex)
    total = 0
    count = 0

    while pq and count < V:
        w, u = heapq.heappop(pq)
        if in_mst[u]:
            continue
        in_mst[u] = True
        total += w
        count += 1
        for v, wt in adj[u]:
            if not in_mst[v]:
                heapq.heappush(pq, (wt, v))

    return total
java
import java.util.*;

class Prim {
    static long solve(int V, List<List<int[]>> adj) {
        boolean[] inMST = new boolean[V];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        pq.offer(new int[]{0, 0});
        long total = 0;
        int count = 0;

        while (!pq.isEmpty() && count < V) {
            int[] cur = pq.poll();
            int w = cur[0], u = cur[1];
            if (inMST[u]) continue;
            inMST[u] = true;
            total += w;
            count++;
            for (int[] e : adj.get(u)) {
                if (!inMST[e[0]]) pq.offer(new int[]{e[1], e[0]});
            }
        }
        return total;
    }
}
go
import "container/heap"

type Item struct{ w, v int }
type PQ []Item
func (pq PQ) Len() int            { return len(pq) }
func (pq PQ) Less(i, j int) bool  { return pq[i].w < pq[j].w }
func (pq PQ) Swap(i, j int)       { pq[i], pq[j] = pq[j], pq[i] }
func (pq *PQ) Push(x interface{}) { *pq = append(*pq, x.(Item)) }
func (pq *PQ) Pop() interface{} {
    old := *pq; n := len(old)
    x := old[n-1]; *pq = old[:n-1]; return x
}

func primMST(V int, adj [][]Item) int {
    inMST := make([]bool, V)
    pq := &PQ{{0, 0}}
    heap.Init(pq)
    total, count := 0, 0

    for pq.Len() > 0 && count < V {
        cur := heap.Pop(pq).(Item)
        if inMST[cur.v] { continue }
        inMST[cur.v] = true
        total += cur.w
        count++
        for _, e := range adj[cur.v] {
            if !inMST[e.v] { heap.Push(pq, e) }
        }
    }
    return total
}

Cut Property — tại sao Kruskal và Prim đúng ​

Định lý: Cho một cut (phân hoạch đồ thị thành hai tập S và V\S), cạnh nhẹ nhất qua cut thuộc ít nhất một MST.

Kruskal kiểm tra mỗi cạnh theo trọng số tăng dần. Cạnh nối hai component khác nhau chính là cạnh nhẹ nhất qua cut ngăn cách hai component đó → thuộc MST. Prim luôn chọn cạnh nhẹ nhất từ tập đã thăm ra tập chưa thăm — cũng chính là cạnh nhẹ nhất qua cut.

Thực chiến ​

Tình huống: Thiết kế mạng chi phí tối thiểu ​

Bối cảnh: N data center cần kết nối. Có M tuyến cáp khả dụng với chi phí khác nhau. Tìm cách kết nối tất cả với chi phí thấp nhất.

python
def design_network(
    num_dc: int,
    cables: list[tuple[str, str, int]],
    dc_names: list[str]
) -> tuple[int, list[tuple[str, str, int]]]:
    name_to_id = {name: i for i, name in enumerate(dc_names)}
    edges = [(name_to_id[u], name_to_id[v], cost)
             for u, v, cost in cables]

    total, mst_edges = kruskal(num_dc, edges)

    result = [(dc_names[u], dc_names[v], w) for u, v, w in mst_edges]
    if len(mst_edges) < num_dc - 1:
        raise ValueError("Cannot connect all data centers")
    return total, result

Phân tích: Kruskal phù hợp vì input dạng edge list. Nếu đồ thị dense (M ≈ V²), Prim với adjacency matrix O(V²) sẽ nhanh hơn.

Sai lầm điển hình ​

❌ Sai lầm 1: Quên kiểm tra đồ thị liên thông ​

Vấn đề: Chạy MST trên đồ thị không liên thông.

python
# SAI: không kiểm tra kết quả
total, mst = kruskal(V, edges)
print(f"MST cost: {total}")  # có thể thiếu cạnh!

Tại sao sai: Nếu đồ thị không liên thông, MST chỉ nối được các component riêng lẻ. Kết quả thiếu cạnh mà không báo lỗi.

python
# ĐÚNG: verify MST có đúng V-1 cạnh
total, mst = kruskal(V, edges)
if len(mst) != V - 1:
    raise ValueError("Graph is not connected — MST doesn't exist")

❌ Sai lầm 2: Prim bỏ quên đỉnh đã thăm ​

Vấn đề: Không kiểm tra in_mst[u] sau khi pop từ priority queue.

python
# SAI: xử lý đỉnh đã thăm → kết quả sai
w, u = heapq.heappop(pq)
total += w  # nếu u đã trong MST, cộng thừa!

Tại sao sai: Priority queue có thể chứa nhiều entry cho cùng một đỉnh. Không kiểm tra sẽ cộng thừa trọng số và tạo cycle.

python
# ĐÚNG: skip đỉnh đã thăm (lazy deletion)
w, u = heapq.heappop(pq)
if in_mst[u]:
    continue
in_mst[u] = True
total += w

❌ Sai lầm 3: Nhầm Prim với Dijkstra ​

Vấn đề: Dùng khoảng cách tích lũy thay vì trọng số cạnh.

python
# SAI: Dijkstra-style — dist[v] = dist[u] + w
heapq.heappush(pq, (dist[u] + w, v))

Tại sao sai: Prim chọn cạnh nhẹ nhất ra ngoài MST, không phải đường đi ngắn nhất. Key trong priority queue là trọng số cạnh, không phải tổng khoảng cách.

python
# ĐÚNG: key là trọng số cạnh, không phải distance
heapq.heappush(pq, (w, v))

Under the Hood ​

Hiệu năng ​

Thuật toánTimeSpaceTốt nhất khi
KruskalO(E log E)O(V + E)Đồ thị thưa (E ≈ V), edge list input
Prim (binary heap)O((V+E) log V)O(V + E)Đồ thị dense, adjacency list
Prim (Fibonacci heap)O(E + V log V)O(V + E)Lý thuyết tối ưu, hiếm dùng thực tế

Kruskal: bottleneck ở sort cạnh O(E log E). DSU operations gần O(1). Tối ưu cho sparse graph khi E ≪ V².

Prim: tương tự Dijkstra. Mỗi đỉnh pop 1 lần từ heap, mỗi cạnh push 1 lần. Tối ưu cho dense graph.

Khi nào MST duy nhất? ​

MST duy nhất khi và chỉ khi không có hai cạnh khác nhau cùng trọng số mà có thể thay thế nhau (cùng là cạnh nhẹ nhất qua một cut). Nếu tất cả trọng số phân biệt, MST luôn duy nhất.

MST và bài toán liên quan ​

  • Minimum bottleneck spanning tree: MST cũng là cây khung có cạnh nặng nhất nhỏ nhất
  • TSP approximation: MST × 2 cho đường Hamilton xấp xỉ ≤ 2 × OPT (metric TSP)
  • Clustering: Xóa k-1 cạnh nặng nhất của MST → k clusters (single-linkage clustering)

Checklist ghi nhớ ​

✅ Checklist triển khai

Kruskal

  • [ ] Sort edges theo weight → duyệt → DSU unite → thêm vào MST nếu union thành công
  • [ ] Dừng sớm khi MST đủ V-1 cạnh
  • [ ] Verify kết quả: len(mst) == V - 1 → đồ thị liên thông

Prim

  • [ ] Min-heap lưu (weight, vertex) — key là trọng số cạnh, KHÔNG phải khoảng cách
  • [ ] Skip đỉnh đã thăm khi pop (lazy deletion)
  • [ ] Tương tự Dijkstra về cấu trúc, nhưng khác ở key

Lựa chọn thuật toán

  • [ ] Sparse graph (E ≈ V) → Kruskal
  • [ ] Dense graph (E ≈ V²) → Prim
  • [ ] Cần edge list cụ thể của MST → Kruskal (tự nhiên hơn)
  • [ ] Đồ thị không liên thông → MST không tồn tại, kiểm tra trước

Bài tập luyện tập ​

Bài 1: Min Cost to Connect All Points — Foundation ​

Đề bài: Cho mảng points[i] = [xi, yi]. Chi phí nối hai điểm = |xi - xj| + |yi - yj|. Tìm chi phí tối thiểu để nối tất cả điểm. (LeetCode 1584)

🧠 Quiz

Kruskal dừng khi nào?

  • [ ] A. Hết cạnh
  • [x] B. MST đủ V-1 cạnh
  • [ ] C. Tất cả đỉnh đã visit
  • [ ] D. Queue rỗng Giải thích: Cây V đỉnh luôn có đúng V-1 cạnh. Kruskal dừng sớm khi MST đủ cạnh — không cần duyệt hết tất cả edges.
💡 Gợi ý
  • Tạo tất cả cạnh (V² cạnh cho V điểm), weight = Manhattan distance
  • Chạy Kruskal hoặc Prim
  • Dense graph (V² edges) → Prim có thể nhanh hơn
✅ Lời giải
python
def minCostConnectPoints(points: list[list[int]]) -> int:
    n = len(points)
    edges = []
    for i in range(n):
        for j in range(i + 1, n):
            d = abs(points[i][0]-points[j][0]) + abs(points[i][1]-points[j][1])
            edges.append((i, j, d))

    total, _ = kruskal(n, edges)
    return total

Phân tích: O(V² log V) time — V² cạnh, sort O(V² log V²) = O(V² log V). Prim O(V²) với adjacency matrix nhanh hơn cho bài này.

Bài 2: Critical/Pseudo-critical Edges in MST — Advanced ​

Đề bài: Phân loại mỗi cạnh thành critical (bắt buộc thuộc mọi MST), pseudo-critical (thuộc ít nhất một MST), hoặc không thuộc MST nào. (LeetCode 1489)

💡 Gợi ý
  • Critical: xóa cạnh → MST weight tăng (hoặc không liên thông)
  • Pseudo-critical: ép cạnh vào MST → MST weight không đổi
  • Thử từng cạnh: O(E²α(V))

Liên kết học tiếp ​

📚 Bài liên quan

Bài liên quan trong Penalgo

Từ khóa glossary: MST, cây khung nhỏ nhất, Kruskal, Prim, cut property, spanning tree, greedy

Tìm kiếm liên quan: cây khung, kết nối mạng chi phí nhỏ nhất, minimum cost network, clustering MST

Professional Engineering Standards | © 2025 HPN Corporation