Thuật toán đồ thị Thuật toán cho các khu vực kết nối tối thiểu với ranh giới chia sẻ

Question

Tôi có biểu đồ trọng số của nhiều "bút động vật" với mỗi bút có ít nhất 3 cạnh/điểm và ít nhất hai bút. Tôi phải tìm ra các cạnh có trọng số tối thiểu để loại bỏ để kết nối tất cả các bút (Bạn có thể kết nối chúng bằng cách loại bỏ các cạnh ngoài không được kết nối với các bút khác).

Ai đó có thể đề xuất thuật toán hoặc quá trình mà tôi có thể tiếp cận việc tìm các bức tường có trọng số tối thiểu để loại bỏ. Tôi đã suy nghĩ về thuật toán của Prim nhưng tôi thậm chí không hoàn toàn chắc chắn làm thế nào tôi có thể áp dụng điều đó.

Đây là vấn đề S4 trên http://cemc.math.uwaterloo.ca/contests/computing/2010/stage1/seniorEn.pdf

Tôi không muốn câu trả lời chỉ là một số hướng như thế nào để tiếp cận nó

Answer 1

Bạn đang đi đúng hướng.

Mẫu vấn đề của bạn như một đồ thị vô hướng G=(V,E) nơi V = { all pens }, E = { (u,v) | there is a wall between u and v } với w((u,v)) = cost of wall between u and v

Để "kết nối tất cả bút" - bạn thực sự đang tìm kiếm một đồ thị con: G'=(V,E') như vậy mà đồ thị phụ G' sẽ được kết nối [ Có một con đường giữa hai nút], và chi phí của các bức tường trong E 'là tối thiểu.

Để làm được điều này với chi phí tối thiểu - bạn đang tìm kiếm Minimum Spanning Tree. [Thật dễ dàng để thấy rằng bạn thực sự cần một cây - vì bất kỳ cạnh thừa nào sau khi tạo cây là thừa và có thể bị xóa mà không làm tổn hại đến kết nối của biểu đồ - hoặc trong thuật ngữ vấn đề - bạn có thể khôi phục một bức tường và bút duy trì kết nối]

Hai thuật toán có thể sẽ giúp bạn có được MST là Prim và Kruskal