Algorithmus, um MST in einem riesigen vollständigen Graph zu finden

Question

Nehmen wir einen vollständigen Graphen von> 25000 Knoten an. Jeder Knoten ist im Wesentlichen ein Punkt in einer Ebene. Es hat 625M Kanten. Jede Kante hat eine Länge, die als Gleitkommazahl gespeichert werden sollte.

Ich brauche einen Algorithmus, um seine MST (auf einem üblichen PC) zu finden.

Wenn ich Kruskals Algorithmus nehme, muss er zuerst alle Kanten sortieren, aber ich kann es mir nicht einmal leisten, die Kanten zusammen im Speicher zur gleichen Zeit zu speichern.

Wenn ich Prims Algorithmus wähle, ist es ziemlich schwierig zu bewerten, wie viele Kanten gleichzeitig in einem Haufen gespeichert werden, aber wahrscheinlich werden die meisten von ihnen sehr bald nach dem Algorithmusstart da sein.

Gibt es einen speichergenauen Algorithmus, mit dem ich die in einer Datei gespeicherten Kanten vermeiden kann?

Gibt es auch bekannte MST-Algorithmen, die die Tatsache nutzen, dass irgendwelche Baumkanten Dreiecksungleichheit erfüllen?

Answer 1

Versuchen dieser Algorithmus

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 

Autor zu verwenden:

Vibhav Vineet  
Pawan Harish  
Suryakant Patidar  
P. J. Narayanan 

Source

Answer 2

Sie noch Kruskal Algorithmus verwenden können.

Sie müssen die Kanten nicht wirklich sortieren, was der Algorithmus erfordert, ist einfach eine Methode, um die kleinste Gewichtskante, die noch nicht benutzt wurde, zu finden. Vorsortieren der Kanten und Iterieren durch diese Liste ist einfach eine sehr effiziente Möglichkeit.

Sie können dasselbe tun, indem Sie einfach die k-kleinsten unbenutzten Kanten (wobei k eine überschaubare Zahl ist, wahrscheinlich mindestens | V |) wiederfinden und dann nach Bedarf sortieren und durchlaufen. Dies unterbricht den Sortierprozess in verwaltbare Segmente, obwohl es einen Zeit-Raum-Kompromiss gibt, abhängig davon, wie groß k ist, dass die Zeitkomplexität dieses Prozesses irgendwo von O (E log E) (k = E) bis etwa O sein kann (E^2) (k = 1).

Answer 3

Boruvka's algorithm erstellt eine logarithmische Anzahl von Durchläufen auf der unsortierten Edge-Liste. Der erforderliche Speicher ist proportional zur Anzahl der Knoten.