Tôi không muốn tìm tất cả các cây bao trùm nhỏ nhất nhưng tôi muốn biết có bao nhiêu trong số đó là ở đó, đây là phương pháp tôi coi:Làm thế nào để tìm tổng số cây bao trùm tối thiểu trong biểu đồ?
- Tìm một tối thiểu spanning tree sử dụng của prim hoặc Thuật toán Kruskal và sau đó tìm các trọng số của tất cả các cây bao trùm và tăng bộ đếm đang chạy khi nó bằng với trọng lượng của cây bao trùm tối thiểu.
Tôi không thể tìm thấy phương pháp nào để tìm trọng số của tất cả các cây bao trùm và số cây bao trùm có thể rất lớn, vì vậy phương pháp này có thể không phù hợp với vấn đề. Vì số lượng cây bao trùm tối thiểu là theo cấp số mũ, nên chúng sẽ không phải là một ý tưởng hay.
- Tất cả trọng số sẽ là số dương.
- Chúng tôi cũng có thể giả định rằng không có trọng lượng nào xuất hiện nhiều hơn ba lần trong biểu đồ.
- Số đỉnh sẽ nhỏ hơn hoặc bằng 40.000.
- Số cạnh sẽ nhỏ hơn hoặc bằng 100.000.
Chỉ có một cây bao trùm tối thiểu trong biểu đồ có trọng số của các đỉnh khác nhau. Tôi nghĩ cách tốt nhất để tìm số cây bao trùm tối thiểu phải là cái gì đó sử dụng thuộc tính này.
EDIT:
Tôi tìm thấy một giải pháp cho vấn đề này, nhưng tôi không chắc chắn, tại sao nó hoạt động. Bất cứ ai có thể vui lòng giải thích nó.
Giải pháp: Vấn đề tìm chiều dài của cây bao trùm tối thiểu khá nổi tiếng; hai thuật toán đơn giản nhất để tìm một cây bao trùm tối thiểu là thuật toán của Prim và thuật toán của Kruskal. Trong hai thuật toán này, thuật toán của Kruskal xử lý các cạnh theo thứ tự tăng dần trọng số của chúng. Tuy nhiên, có một điểm quan trọng trong thuật toán của Kruskal để xem xét: khi xem xét một danh sách các cạnh được sắp xếp theo trọng lượng, các cạnh có thể được thêm vào trong cây spanning (miễn là chúng không kết nối hai đỉnh đã được kết nối theo một cách nào đó)).
Bây giờ, hãy xem xét cây bao trùm hình thành một phần bằng thuật toán của Kruskal. Chúng tôi đã chèn một số cạnh có độ dài nhỏ hơn N, và bây giờ phải chọn một số cạnh dài N. Thuật toán nói rằng chúng ta phải chèn các cạnh này, nếu có thể, trước bất kỳ cạnh nào có độ dài lớn hơn N. Tuy nhiên, chúng ta có thể chèn các cạnh này theo bất kỳ thứ tự nào mà chúng ta muốn. Cũng lưu ý rằng, không có vấn đề gì cạnh chúng tôi chèn, nó không thay đổi kết nối của đồ thị ở tất cả. (Chúng ta hãy xem xét hai đồ thị có thể, một với một cạnh từ đỉnh A đến đỉnh B và một không có. Biểu đồ thứ hai phải có A và B như là một phần của cùng một thành phần được kết nối, nếu không thì cạnh từ A đến B sẽ được chèn vào một điểm.)
Hai sự kiện này cùng nhau ngụ ý rằng câu trả lời của chúng tôi sẽ là sản phẩm của số cách, sử dụng thuật toán của Kruskal, để chèn các cạnh của độ dài K (cho mỗi giá trị có thể của K). Vì có tối đa ba cạnh của bất kỳ độ dài nào, các trường hợp khác nhau có thể bị cưỡng bức, và các thành phần được kết nối có thể được xác định sau mỗi bước như bình thường.
sự cố mà tôi đang cố giải quyết có cạnh tối đa 100.000. Vì vậy, nó sẽ mất một thời gian dài để chạy thuật toán của prim từ mỗi cạnh. – 2147483647
Bạn có thể tăng tốc độ bằng cách kiểm tra xem có bất kỳ đồ thị trung gian nào là biểu đồ mà bạn đã gặp phải dưới dạng biểu đồ trung gian chưa. Bất kỳ đồ thị như vậy chắc chắn sẽ mang lại những cây bao trùm tối thiểu mà chúng ta đã có. Mặc dù điều này sẽ chi phí bạn trong bộ nhớ. Ở mức nào, nó sẽ vẫn chậm. – bowmore
Bạn có thể chạy thuật toán cho mỗi cạnh bắt đầu đồng thời: bắt đầu bằng cách tạo một khu rừng của tất cả các cây là kết quả của bước đầu tiên trong thuật toán của Prim. (từ 40k đỉnh này cho năng suất abt. 20k cây) Sau đó thực hiện bước tiếp theo của thuật toán trên mỗi cây trong khu rừng đó, và tạo một khu rừng mới chứa cây với hai cạnh (có khả năng loại bỏ nhiều bản sao hơn). Mỗi bước sẽ tiếp tục loại bỏ các bản sao, và cấu trúc này cũng dễ dàng cho phép xử lý nhiều khả năng như bước tiếp theo bằng cách thêm tất cả các khả năng vào rừng thế hệ tiếp theo – bowmore