Những cây có kích thước tối thiểu được dùng để kết nối tất cả các nút trong một đồ thị với trọng lượng ít nhất là bằng một cạnh.

Thuật toán của Krussal

Thuật toán của Kruskal loại tất cả các cạnh trong đồ thị bằng trọng lượng, rồi thêm các cạnh vào cây trải dài, bắt đầu từ những vòng tròn nhỏ nhất, không có chu kỳ nào được hình thành.

Thuật toán này đặc biệt hiệu quả cho đồ thị rời rạc. Nó sử dụng một cấu trúc thiết lập dữ liệu không khớp để kiểm tra hiệu quả nếu thêm một cạnh sẽ tạo ra một chu kỳ.

Thuật toán của Prim

Thuật toán của Prim bắt đầu từ một nút tùy ý và mọc những cái cây liên tục bằng cách thêm cạnh nhỏ nhất nối cây với một nút mới, và tiếp tục cho đến khi tất cả các nút đều được tính vào.

Phương pháp này thường được ưu tiên cho đồ thị đặc. Nó dùng hàng đợi ưu tiên để chọn cạnh kế tiếp với trọng lượng tối thiểu hiệu quả.

So sánh và giải thoát

Cả hai thuật toán bảo đảm tìm ra cây có độ dài tối thiểu, nhưng hiệu quả của nó tùy thuộc vào cấu trúc của đồ thị.

  • Những cạnh loại của Krukal trên toàn cầu
  • Prim mọc cây từ một nút bắt đầu
  • Cả hai đều sử dụng cấu trúc dữ liệu khác nhau để hiệu quả
  • Lựa chọn phụ thuộc vào mật độ và kích cỡ biểu đồ