Lesson 35 — Cây khung nhỏ nhất (MST): Kruskal & Prim

Ba module tương tác cho Minimum Spanning Tree: Kruskal (sort cạnh + Union-Find từ chối chu trình), Prim (grow cây từ một đỉnh bằng min-heap), và so sánh song song — cùng đồ thị, hai thuật toán, cùng MST weight.

1. Kruskal — sort cạnh + Union-Find O(E log E)

Cạnh được sort tăng dần. Mỗi bước lấy cạnh nhẹ nhất còn lại: nếu hai đầu khác thành phần → thêm vào MST + union; nếu cùng thành phần → bỏ (tạo chu trình).

chưa xét đang xét trong MST bị từ chối (chu trình)

Cạnh đã sort (tăng dần):

Thành phần (Union-Find):

Bấm "Bước tiếp" để bắt đầu.

Tổng trọng số MST: 0

2. Prim — grow cây từ một đỉnh + min-heap O(E log V)

Bắt đầu từ đỉnh 0. Heap chứa các cạnh biên (nối cây ↔ đỉnh ngoài). Mỗi bước pop cạnh nhẹ nhất: nếu đỉnh đích đã trong cây → bỏ (lỗi thời); nếu ngoài → thêm đỉnh + cạnh vào cây, push cạnh biên mới.

đỉnh ngoài đỉnh trong cây cạnh cây cạnh đang xét

Min-heap (cạnh biên, sắp theo trọng số):

Bấm "Bước tiếp" để bắt đầu.

Tổng trọng số MST: 0

3. Kruskal vs Prim — cùng đồ thị, cùng weight so sánh

Chạy cả hai trên cùng đồ thị. Thứ tự thêm cạnh có thể khác, nhưng tổng trọng số MST luôn bằng nhau (MST weight là duy nhất).

Kruskal

Thứ tự thêm: —

Weight: —

Prim (từ đỉnh 0)

Thứ tự thêm: —

Weight: —

Bấm "Chạy cả hai" để so sánh.