Ist diese dichte Version von Kruskals Algorithmus bekannt?

Vor ungefähr einem Jahr dachten ein Freund und ich über eine Möglichkeit nach, den Kruskal-Algorithmus für dichte Graphen besser als in der üblichen Grenze ( zu implementieren (ohne die Annahme von vorsortierten Kanten). Insbesondere erreichen wir in allen Fällen , ähnlich wie bei Prims, wenn sie unter Verwendung von Adjazenzmatrizen implementiert werden.Θ ( n 2$O(m \log m)$$\Theta(n^2)$

Ich habe ein bisschen über den Algorithmus in meinem Blog geschrieben , einschließlich C ++ - Code und Benchmarks, aber hier ist die allgemeine Idee:

• Pflegen Sie für jede angeschlossene Komponente einen repräsentativen Knoten. Anfangs repräsentieren sich alle Knoten.

• Pflegen Sie einen Vektor dist[i]so, dass für jede Komponente idie leichteste Kante auftritt, die die Komponente kreuzt i.

• Wenn Sie die leichteste Kante finden, die Partitionen überquert, müssen Sie einfach in linearer Zeit idas Gewicht von minimieren dist[i].

• Wenn Sie zwei Komponenten und , ändern Sie die Adjazenzmatrix so, dass nun für alle Komponenten und markieren i als nicht mehr repräsentativ für seine angeschlossene Komponente (nur j bleibt jetzt übrig).$c_i$$c_j$$A$$A_{i, k} = \min \{A_{i, k}, A_{j, k}\}$$k$$i$$j$

Das Zusammenziehen der leichtesten Kante und das Auffinden dieser Kante kann somit beide in linearer Zeit erfolgen. Wir machen dies $n - 1$ mal, um den MST zu finden. Ein wenig Buchhaltung ist erforderlich, um tatsächlich herauszufinden, welche Kante wir dem MST hinzufügen möchten, erhöht jedoch nicht die Komplexität. Die Laufzeit ist also $\Theta(n^2)$ . Die Implementierung ist nur ein paar für Schleifen.

Ist diese Version von Kruskal in der Literatur bekannt?

Ich bin mir nicht sicher über diese spezielle Methode zur Erzielung von -Zeit, aber zwei verschiedene Methoden zur Durchführung von Kruskal in -Zeit sind in meinem Artikel "Schnelles hierarchisches Clustering und andere Anwendungen von dynamischen engsten Paaren" beschrieben (SODA 1998, arXiv: cs.DS / 9912014 und J. Experimental Algorithms 2000):$O(n^2)$$O(n^2)$

1. Verwenden Sie stattdessen Prim – Dijkstra – Jarník und sortieren Sie die Kanten, um die Einfügesequenz zu erhalten, die Kruskal geben würde, oder

2. Verwenden Sie die in diesem Artikel beschriebene Datenstruktur für das nächste Quadtree-Paar und betrachten Sie Kruskal als ein standardmäßiges agglomeratives Clustering-Verfahren, bei dem die nächsten beiden Cluster in jedem Schritt zu einem Supercluster zusammengeführt werden. "Am nächsten" ist dabei die Länge der kürzesten Kante, die zwei Cluster verbindet .

Lösung 2 ähnelt Ihrer Beschreibung im Grunde, aber die Details zur Verfolgung der Abstände zwischen Clustern unterscheiden sich geringfügig. Sie behalten die zeilenweisen Minima der Clusterdistanzmatrix bei, sodass Sie diese Liste der Zeilenminima in linearer Zeit scannen können, um das globale Minimum zu finden, während meine Arbeit einen Quadtree auf derselben Matrix überlagert und das Minimum in jedem nachverfolgt Quadtree Square. Ihre Methode ist einfacher, aber für einige andere dynamische Probleme mit engsten Paaren weniger flexibel (dies hängt davon ab, dass durch das Zusammenführen von zwei Clustern die Abstände zu anderen Clustern verringert werden, was für dieses Problem zutrifft, für andere jedoch nicht unbedingt).

Wie ich 2011 in dem Wikipedia-Artikel über den Algorithmus der Kette der nächsten Nachbarn schrieb, kann dieser Algorithmus auch verwendet werden, um Kruskal in -Zeit durchzuführen . Im Gegensatz zu einigen anderen Anwendungen des Algorithmus für die Kette der nächsten Nachbarn wird jedoch kein Platz gespart. Daher ist der Platz (wie bei der Quadtree-Methode und Ihrer Methode) immer noch . Im Gegensatz dazu kann bei der Prim + -Sortierung nur der -Raum verwendet werden, der zum Speichern der Eingabe erforderlich ist.$O(n^2)$$O(n^2)$$O(n)$