Thành phố Cuồng loạn

Bài toán yêu cầu tìm cách xây dựng hệ thống đường bộ nối tất cả các hòn đảo với tổng chiều dài ngắn nhất. Đây chính là bài toán tìm cây khung nhỏ nhất (Minimum Spanning Tree - MST) trên đồ thị vô hướng có trọng số. Đầu vào gồm số đỉnh V và số cạnh E, tiếp theo là E dòng mô tả các cạnh với định dạng: đỉnh đầu, đỉnh cuối, trọng số. Đầu ra là tổng ...

Cây Kruskal tái cấu trúc (Kruskal Reconstruction Tree) Quy trình xây dựng cây Kruskal tái cấu trúc: Mỗi đỉnh trong đồ thị gốc là một nút lá của cây Kruskal tái cấu trúc, ban đầu chúng không liên thông với nhau. Xét các cạnh có trọng số nhỏ trước, sau đó đến các cạnh có trọng số lớn. Nếu cạnh giúp tăng tính liên thông thì được chọn, nếu không t ...