cây bao trùm Euclid

[Doc_Co]

Cho trước N điểm trong mặt phẳng, hãy tìm tập các đoạn thẳng nối tất cả các diểm với nhau sao cho tổng dộ dài của chúng ngắn nhất.

Có một cách giả đơn giản nhất là xây dựng một đồ thị đầy đủ cos n đỉnh vaf
n*(n-1)/2 cạnh có trọng số là khoảng cách giữa hai đỉnh . Sau đó dùng Kruskal để tìm.

Xin hỏi:
1. có tài liệu nào hướng dẩn không. Lợi dụng yếu tố hình học ta sẽ loại bỏ một số cạnh trong đô thị đầy đủ trước khi tìm cây bao trùm tối thiểu.

[mhz_bk]

Tài liệu hướng dẫn là cuốn Cẩm nang thuật toán. Đúng là có thể lợi dụng tính chất hình học để loại phần lớn các phép thử khi tìm cây bao trùm