Động lực

Trong khi Kruskal sắp xếp toàn bộ các cạnh trên toàn cục và dùng cấu trúc hợp nhất-tìm kiếm, Prim giữ một cây đang phát triển và liên tục tìm đỉnh bên ngoài gần nhất.

Tại sao nên học Prim?

• Đồ thị dày: Prim hoạt động hiệu quả khi có nhiều cạnh nếu dùng cấu trúc phù hợp.
• Tính chất lát cắt: đây là minh họa trực quan cho lý do cạnh rẻ nhất nối cây hiện tại với bên ngoài luôn an toàn để thêm vào.
• Hai cách nhìn về cùng một bài toán: so sánh Prim và Kruskal giúp bạn hiểu sâu hơn về cây khung nhỏ nhất.

Vì mọi cây khung nhỏ nhất của một đồ thị đều có cùng trọng số cạnh, Prim và Kruskal luôn cho cùng một tổng trọng số.