Khác biệt giữa bản sửa đổi của “Thuật toán Kruskal”

 

*Có thể đạt được thời gian này bằng phương pháp sau: [[thuật toán sắp xếp|sắp xếp]] tất cả các cạnh theo trọng số trong thời gian ''O''(''E'' log ''E''). Điều này cho phép thực hiện bước "xóa cạnh nhỏ nhất trong ''S''" trong thời gian hằng số. Sau đó sử dụng [[cấu trúc dữ liệu cho các tập hợp không giao nhau]] để lưu trữ thông tin đỉnh nào nằm ở cây nào trong ''F''. Ta cần thực hiện O(''E'') thao tác, hai thao tác 'tìm' và không quá một thao tác 'hợp' cho mỗi cạnh. Ngay cả những thuật toán đơn giản cho bài toán này, chẳng hạn hợp bằng trọng số cũng có thể thực hiện O(''E'') thao tác trong thời gian ''O''(''E'' log ''V''). Vì vậy tổng thời gian là ''O''(''E'' log ''E'') = ''O''(''E'' log ''V'').

 

== Cải tiến thuật toán ==