App: thiết kế mạng với Prim và Kruskal

Giới thiệu

Bài này xây app đi dây cáp rẻ nhất nối mọi trạm. Hai thuật toán cùng cho tổng chi phí tối thiểu.

Kiến thức cần nhớ

Kruskal thêm cạnh rẻ nhất

• Sắp xếp mọi cạnh tăng dần rồi thêm dần.
• Dùng Union-Find để bỏ cạnh tạo chu trình.
• Union-Find có nén đường đi nên gần như $O(1)$.
• Ví dụ đời thường: nối dây rẻ nhất mà không tạo vòng lặp.

Prim mọc cây từ 1 nút

• Bắt đầu từ 1 nút, luôn thêm cạnh rẻ nhất ra ngoài.
• Dùng heap để lấy cạnh biên rẻ nhất.
• Đồ thị rời thì cho rừng khung mỗi phần 1 cây.
• Ví dụ đời thường: xây khu dân cư lan dần từ nhà đầu tiên.

So sánh và kiểm đúng

• Kruskal thắng trên đồ thị thưa vì ít cạnh cần sắp.
• Prim thắng trên đồ thị dày vì không sắp hết cạnh.
• Cây đúng có V-1 cạnh, liên thông, tổng trọng số bằng nhau.
• Cut property: cạnh rẻ nhất qua mọi lát cắt thuộc về MST.

Ví dụ

• Input: đồ thị tay 8 nút tính tay trước. Output: 2 thuật toán cho cùng tổng trọng số.
• Giải thích: cả 2 đều tối ưu nên tổng bằng nhau dù cây có thể khác.
• Input: cấm 5 cạnh rẻ nhất rồi chạy lại. Output: tổng chi phí tăng vài phần trăm.
• Giải thích: mất cạnh rẻ nên phải dùng cạnh đắt hơn.

💻 Bài tập

Ngôn ngữ: C++ (hoặc Python). Dùng code ngày 33, 43. Nộp vào day-135-network/.

Bài 1: Thiết kế mạng cáp quang

Dữ liệu: 200 tòa nhà có tọa độ. Chi phí kéo cáp giữa 2 tòa = khoảng cách Euclid x 1.2 triệu/km. Có 30 cặp tòa không kéo trực tiếp được (qua sông).

1. Dựng đồ thị đầy đủ trừ 30 cặp cấm.
2. Chạy Kruskal và Prim. In tổng chi phí (phải bằng nhau) và số cạnh (V - 1).
3. Viết verifyMST(G, T): kiểm tra liên thông, đúng V - 1 cạnh, và cut property: với mỗi cạnh ngoài cây, nó không rẻ hơn cạnh đắt nhất trên đường nối trong cây.

Bài 2: Thưa và dày

đồ_thị            V        E           Kruskal(ms)   Prim_heap(ms)   Prim_mảng O(V^2)(ms)
thưa              10^5     3*10^5      ...
dày               3000     ~4.5*10^6   ...

Kết luận: đồ thị nào hợp thuật toán nào.

Bài 3: Yêu cầu thực tế (nâng cao)

1. Dự phòng: tìm cây khung nhỏ thứ hai (thay 1 cạnh). In chi phí tăng thêm.
2. Bắt buộc: 5 cạnh đã có sẵn (chi phí 0) phải nằm trong mạng. Sửa Kruskal để dùng chúng trước.
3. Giới hạn bậc: trạm trung tâm tối đa 4 kết nối. Viết heuristic và so chi phí với MST không giới hạn.
4. Vẽ mạng trên bản đồ tọa độ.

✅ Tiêu chí hoàn thành

• Kruskal và Prim cùng tổng chi phí, verifyMST pass.
• Bảng thưa/dày có số thật.
• 3 yêu cầu Bài 3 có kết quả và giải thích.
• Có hình mạng.

❓ Câu hỏi ôn tập

• Kruskal tránh chu trình bằng cấu trúc nào?
• Prim chọn cạnh tiếp theo thế nào?
• Đồ thị thưa nên dùng thuật toán nào?
• Kiểm tra cây khung đúng bằng 3 dấu hiệu nào?

🌕 Bạn đã hoàn thành ngày 135. Làm hết bài tập phía trên rồi sang ngày tiếp theo.