Thuật toán Prim
Hãy tưởng tượng kéo cáp từ một nhà máy điện: bạn nối thị trấn gần nhất trước, rồi đến thị trấn nào gần nhất với bất kỳ nơi nào đã được nối, và cứ thế tiếp tục. Đó là thuật toán Prim, và nó luôn kết thúc với mạng lưới rẻ nhất có thể.
Ý tưởng
Cây khung nhỏ nhất nối mọi đỉnh của một đồ thị có trọng số với tổng độ dài cạnh nhỏ nhất có thể. Thuật toán Prim xây dựng nó bằng cách phát triển một cây từ điểm xuất phát ra ngoài. Cây không bao giờ tách thành nhiều mảnh: ở mỗi bước, đúng một đỉnh mới gia nhập, qua cạnh ngắn nhất đi ra khỏi cây.
Từng bước
Đưa điểm xuất phát vào cây. Với mỗi đỉnh ngoài cây, giữ cạnh tốt nhất của nó: cạnh ngắn nhất nối nó với bất kỳ đỉnh nào trong cây. Rồi lặp lại: chọn đỉnh bên ngoài có cạnh tốt nhất ngắn nhất, thêm nó vào cây cùng cạnh đó, và xét các cạnh của nó. Một đỉnh kề ngoài cây giờ có thể đến được bằng cạnh ngắn hơn sẽ nhận cạnh đó làm cạnh tốt nhất mới. Dừng khi mọi đỉnh đã ở trong cây.
Một ví dụ
Lấy các cạnh A–B dài 1, B–C 2, A–C 3, C–D 4 và B–D 5, bắt đầu từ A. Các cạnh của A cho B cạnh tốt nhất 1 và C cạnh tốt nhất 3. B gần nhất nên gia nhập qua A–B; các cạnh của nó cải thiện C thành 2 và cho D 5. C gia nhập qua B–C, và cạnh C–D của nó cải thiện D thành 4. Cuối cùng D gia nhập qua C–D. Cây A–B, B–C, C–D có tổng độ dài 1 + 2 + 4 = 7.
Vì sao đúng
Ở mỗi bước, các đỉnh được chia thành hai nhóm: trong cây và ngoài cây. Tính chất lát cắt nói rằng cạnh ngắn nhất giữa hai nhóm như vậy luôn thuộc về một cây khung nhỏ nhất nào đó. Prim luôn thêm đúng cạnh đó, nên cây đã xây đến lúc đó luôn có thể hoàn thiện thành một cây khung nhỏ nhất, và khi mọi đỉnh đã gia nhập, nó chính là một cây khung nhỏ nhất.
Lịch sử và tốc độ
Nhà toán học Séc Vojtěch Jarník công bố thuật toán năm 1930. Robert Prim tìm lại nó tại Bell Labs năm 1957, và Edsger Dijkstra một lần nữa năm 1959. Khi giữ các đỉnh đang chờ trong heap nhị phân, khối lượng công việc tăng theo E log V với V đỉnh và E cạnh; với một mảng thường thì khoảng V², tốt hơn khi gần như mọi cặp đỉnh đều được nối. Với heap Fibonacci thì là E + V log V.
Khám phá
Mở ứng dụng, nhấp vào một đỉnh để bắt đầu từ đó, rồi nhấn Bước. Các đỉnh trong cây màu xanh lá, các đỉnh đang chờ màu xanh dương, và cạnh tốt nhất của mỗi đỉnh đang chờ được vẽ nét đứt. Các đỉnh đang chờ được liệt kê dưới đồ thị kèm độ dài cạnh tốt nhất, ngắn nhất đứng đầu: đỉnh đầu tiên sẽ gia nhập tiếp theo. Hãy bắt đầu từ các đỉnh khác nhau và xem thứ tự thay đổi trong khi tổng vẫn giữ nguyên.
Câu hỏi thường gặp
Thuật toán Prim và thuật toán Dijkstra khác nhau thế nào?
Cả hai đều mở rộng một vùng từ điểm xuất phát bằng hàng đợi ưu tiên. Prim xếp hạng một đỉnh đang chờ theo độ dài của một cạnh tốt nhất nối nó với cây; Dijkstra xếp hạng theo toàn bộ khoảng cách từ điểm xuất phát. Prim cho cây khung nhỏ nhất, Dijkstra cho cây đường đi ngắn nhất.
Thuật toán Prim có dùng được với độ dài cạnh âm không?
Có. Không như thuật toán Dijkstra, Prim chỉ so sánh các cạnh với nhau, nên độ dài âm không gây vấn đề gì: nó vẫn tìm được cây khung có tổng nhỏ nhất.
Nếu đồ thị không liên thông thì sao?
Khi đó thuật toán Prim dừng lại sau khi đến được mọi đỉnh có thể: nó chỉ cho cây khung nhỏ nhất của phần chứa điểm xuất phát. Chạy lại từ một đỉnh chưa đến được sẽ cho một rừng khung nhỏ nhất.
Thuật toán Prim hay Kruskal tốt hơn?
Không thuật toán nào luôn thắng. Prim hợp với đồ thị dày và đồ thị lưu dưới dạng danh sách đỉnh kề; Kruskal hợp với đồ thị thưa cho dưới dạng danh sách cạnh. Cả hai đều tìm được cây có cùng tổng độ dài.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Thử thuật toán Prim