[Thuật toán] Tìm cây khung nhỏ nhất

Bài toán cây khung nhỏ nhất của đồ thị là một trong số những bài toán tối ưu trên đồ thị được ứng dụng trong nhiều lĩnh vực khác nhau của đời sống. Trong mục này chúng ta sẽ trình bày những thuật toán cơ bản để giải bài toán này. Trước hết chúng ta phát biểu nội dung của bài toán.     ...

[Thuật toán] Kruskal - Tìm cây khung nhỏ nhất

Xem thuật toán Prim - tìm cây khung nhỏ nhất tại đây. Thuật toán sẽ xây dựng tập cạnh T của cây khung nhỏ nhất H=<V, T> theo từng bước như sau: 1.  Sắp xếp các cạnh của đồ thị G theo thứ tự tăng dần của trọng số cạnh; 2.  Xuất phát từ tập cạnh T=φ, ở...