Tiêu đề: So sánh Kruskal và Prim 21/5/2010, 10:46 am
- Do thuật toán Kruskal làm việc trên các cạnh nên sẽ kém hiệu quả nếu có quá nhiều cạnh? như các đồ thị dày (số cạnh m ≈ n(n-1)/2). - Đối nghịch với Kruskal, thuật toán Prim làm việc trên các đỉnh, sẽ hiệu quả hơn với các đồ thị dày. Có thế thấy đa số các đồ thị trong thực tế có số đỉnh không lớn còn số cạnh rất lớn nên Prim tỏ ra hiệu quả hơn và?đắt giá? hơn Kruskal, mặc dù cài đặt có phức tạp hơn. Ngoại lệ, trong các trường hợp số cạnh rất ít còn số đỉnh rất nhiều thì Prim kém hiệu quả hơn Kruskal.