Cây khung nhỏ nhất — Prim & Kruskal

Bạn sẽ học được gì

Cây khung nhỏ nhất (MST — Minimum Spanning Tree) là tập cạnh nối liền tất cả các đỉnh với tổng trọng số nhỏ nhất và không có chu trình. Bạn sẽ học hai cách kinh điển: Prim (mở rộng dần bằng heap) và Kruskal (sắp cạnh tăng dần + Union-Find).

1. Trực quan: nối làng bằng đường rẻ nhất

Có nhiều ngôi làng, bạn muốn xây đường nối tất cả chúng với tổng chi phí thấp nhất. Không cần nối mọi cặp — chỉ cần liên thông. Kết quả là một cây (V đỉnh, V-1 cạnh, không vòng) có tổng trọng số nhỏ nhất.

   Do thi (trong so tren canh):

        1        3
   A ------ B ------ C
   |        |        |
  4|       2|       5|
   |        |        |
   D ------ E ------ F
        6        1

   MST chon: A-B(1), B-E(2), E-F(1), B-C(3), A-D(4)
   Tong = 1+2+1+3+4 = 11, dung 5 canh noi 6 dinh.

2. Hai chiến lược tham lam

	Prim	Kruskal
Ý tưởng	Lớn dần một cây từ một đỉnh	Gom cạnh rẻ nhất, tránh tạo vòng
Công cụ	Heap chọn cạnh rẻ nhất ra biên	Sắp cạnh + Union-Find
Hợp với	Đồ thị dày (nhiều cạnh)	Đồ thị thưa, danh sách cạnh

Cả hai đều tham lam nhưng đều cho ra MST tối ưu nhờ "tính chất cắt": cạnh nhẹ nhất băng qua một lát cắt luôn nằm trong MST nào đó.

3. Chạy debug: Prim

🐞 Prim bắt đầu từ ABước 1/8

1import heapq
2g = {"A":[("B",1),("D",4)], "B":[("A",1),("C",3)], "C":[("B",3)], "D":[("A",4)]}
3seen = {"A"}; pq = [(1,"A","B"), (4,"A","D")]; mst = []
4while pq:
5  w, u, v = heapq.heappop(pq)
6  if v in seen:
7      continue
8  seen.add(v); mst.append((u, v, w))
9  for x, wx in g[v]:
10      if x not in seen:
11          heapq.heappush(pq, (wx, v, x))

Biến tại bước này

seen	{A}
pq	[(1,A,B),(4,A,D)]
mst	[]

👉 Bắt đầu từ A, đẩy các cạnh ra biên.

4. Code chạy được

Đang tải trình chạy code…

5. Kruskal — sắp cạnh + Union-Find

Kruskal đi từ góc nhìn cạnh: sắp toàn bộ cạnh tăng dần theo trọng số, rồi lần lượt nhận cạnh nào không tạo chu trình. Để biết hai đầu cạnh đã cùng một nhóm chưa, ta dùng Union-Find.

Đang tải trình chạy code…

6. Phân tích & so sánh

Thuật toán	Thời gian	Cấu trúc chính
Prim (binary heap)	O(E log V)	Hàng đợi ưu tiên
Kruskal	O(E log E)	Sắp xếp + Union-Find

Bẫy thường gặp:

• Quên kiểm tra v in seen (Prim) hoặc cùng nhóm (Kruskal) → tạo chu trình, sai MST.
• MST yêu cầu đồ thị liên thông; nếu không sẽ chỉ ra rừng khung (spanning forest).
• MST làm việc với trọng số cạnh, không liên quan tới đường đi ngắn nhất.

7. Mẫu nhận diện

• "Nối tất cả các điểm với chi phí nhỏ nhất", "kéo cáp / xây đường rẻ nhất" → MST.
• Dữ liệu cho dạng danh sách cạnh → Kruskal thường tiện hơn.
• Đồ thị dày hoặc cho dạng danh sách kề → Prim với heap.

8. 🎮 Trò chơi: Hiểu MST

🎮 Hiểu MST (Prim & Kruskal)Câu 1/4· Điểm 0· 🔥 0

MST: nối hết đỉnh, tổng trọng số nhỏ nhất, không chu trình, đúng V-1 cạnh.

Prim mở rộng cây bằng cách luôn chọn?

9. Quiz kiểm tra nhanh

📝 Quiz kiểm tra nhanh

1. MST là gì?

2. Độ phức tạp của Kruskal chủ yếu đến từ?

3. Prim thường được cài bằng cấu trúc nào để chọn cạnh rẻ nhất?

10. Hoàn thành

…

☑️ Tiếp theo: 3.3.7 — Union-Find (DSU) (cấu trúc đứng sau Kruskal).