Thuật toán để tìm MST trong đồ thị hoàn chỉnh lớn

Question

Giả sử một đồ thị hoàn chỉnh> 25.000 nút. Mỗi nút về cơ bản là một điểm trên mặt phẳng. Nó có cạnh 625M. Mỗi cạnh có độ dài cần được lưu trữ dưới dạng số dấu phẩy động.

Tôi cần một thuật toán để tìm MST của nó (trên PC thông thường).

Nếu tôi sử dụng thuật toán của Kruskal, trước tiên cần sắp xếp tất cả các cạnh, nhưng tôi không thể đủ khả năng lưu trữ các cạnh hoàn toàn trong bộ nhớ cùng một lúc.

Nếu tôi chọn thuật toán của Prim, rất khó để đánh giá số lượng cạnh sẽ được lưu trữ trong cùng một lúc, nhưng có lẽ hầu hết chúng sẽ xuất hiện ngay sau khi thuật toán bắt đầu.

Có thêm thuật toán đủ bộ nhớ nào có thể cho phép tôi tránh sắp xếp các cạnh được lưu trữ trong tệp không?

Ngoài ra, có bất kỳ thuật toán MST nào đã biết sử dụng thực tế rằng bất kỳ cạnh cây nào thỏa mãn bất bình đẳng tam giác không?

Answer 1

Cố gắng sử dụng thuật toán này

1: Append weight w and outgoing vertex v per edge into a list, X. 
2: Divide the edge-list, E, into segments with 1 indicating the start 
of each segment, and 0 otherwise, store this in flag array F. 
3: Perform segmented min scan on X with F indicating segments 
to find minimum outgoing edge-index per vertex, store in NWE. 
4: Find the successor of each vertex and add to successor array, S. 
5: Remove cycle making edges from NWE using S, and identify 
representatives vertices. 
6: Mark remaining edges from NWE as part of output in MST. 
7: Propagate representative vertex ids using pointer doubling. 
8: Append successor array’s entries with its index to form a list, L 
9: Split L, create flag over split output and scan the flag to find 
new ids per vertex, store new ids in C. 
10: Find supervertex ids of u and v for each edge using C. 
11: Remove edge from edge-list if u, v have same supervertex id. 
12: Remove duplicate edges using split over new u, v and w. 
13: Compact and create the new edge-list and weight list . 
14: Build the vertex list from the newly formed edge-list. 
15: Call the MST Algorithm on 

Tác giả:

Vibhav Vineet  
Pawan Harish  
Suryakant Patidar  
P. J. Narayanan 

Source

Answer 2

Bạn vẫn có thể sử dụng Thuật toán Kruskal.

Bạn không thực sự cần phải sắp xếp các cạnh, thuật toán yêu cầu chỉ đơn giản là phương pháp lặp lại việc tìm kiếm cạnh trọng lượng nhỏ nhất chưa được sử dụng. Việc sắp xếp các cạnh và lặp qua danh sách đó chỉ đơn giản là một cách rất hiệu quả để làm như vậy. Bạn có thể làm điều tương tự đơn giản bằng cách lặp lại tìm các cạnh không sử dụng k-nhỏ nhất (trong đó k là một số có thể quản lý, có thể ít nhất | V |), sau đó sắp xếp và lặp qua chúng thay vào khi cần thiết. Điều này phá vỡ quá trình phân loại thành các phân đoạn dễ quản lý hơn, mặc dù có sự cân bằng không gian thời gian tùy thuộc vào độ phức tạp thời gian của quá trình này có thể ở bất kỳ đâu từ O (E log E) (k = E) đến khoảng O (E^2) (k = 1).

Answer 3

Boruvka's algorithm tạo số lượng vượt qua lôgarit trên danh sách cạnh chưa phân loại. Bộ nhớ được yêu cầu tỷ lệ thuận với số lượng nút.