Czy ta gęsta wersja algorytmu Kruskala jest dobrze znana?

Mniej więcej rok temu razem z przyjacielem zastanawialiśmy się, jak zaimplementować algorytm Kruskala dla gęstych wykresów w lepszej niż zwykle granicy $O(m \log m)$ (bez zakładania wstępnie posortowanych krawędzi). Konkretnie, osiągamy $\Theta(n^2)$ we wszystkich przypadkach, podobnie jak Prim, gdy implementujemy je za pomocą macierzy sąsiedztwa.

Na blogu opublikowałem trochę informacji o algorytmie, w tym kod C ++ i testy porównawcze, ale oto ogólny pomysł:

• Utrzymaj jeden reprezentatywny węzeł dla każdego podłączonego komponentu. Początkowo wszystkie węzły reprezentują siebie.

• Zachowaj wektor dist[i]taki, że dla każdego komponentu ima najlżejsze uderzenie krawędzi przecinającej komponent i.

• Znajdując najlżejszą krawędź przecinającą partycje, po prostu znajdź, iktóra minimalizuje wagę dist[i]w czasie liniowym.

• $c_i$$c_j$$A$$A_{i, k} = \min \{A_{i, k}, A_{j, k}\}$$k$$i$$j$

Skurczenie najlżejszej krawędzi i znalezienie wspomnianej krawędzi można zatem wykonać w czasie liniowym. Robimy to razy, aby znaleźć MST. Potrzebna jest niewielka księgowość, aby znaleźć krawędź, którą chcemy dodać do MST, ale nie zwiększa to złożoności. Tak więc środowisko wykonawcze to . Implementacja to tylko kilka pętli.$n - 1$$\Theta(n^2)$

Czy ta wersja Kruskala jest dobrze znana w literaturze?

Nie jestem pewien co do tej konkretnej metody osiągania czasu , ale dwie różne metody przeprowadzania Kruskala w czasie podane są w moim artykule „Szybkie grupowanie hierarchiczne i inne zastosowania dynamicznych najbliższych par „(SODA 1998, arXiv: cs.DS / 9912014 i J. Experimental Algorithms 2000):$O(n^2)$$O(n^2)$

1. Zamiast tego użyj Prim – Dijkstra – Jarník, a następnie posortuj krawędzie, aby uzyskać sekwencję wstawiania, którą dałby Kruskal, lub

2. Użyj struktury danych z najbliższej pary z czterema drzewami opisanej w artykule, traktując Kruskala jako standardową procedurę skupiania aglomeracyjnego, w której na każdym etapie łączymy dwie najbliższe klastry w supergromadę, przy czym „najbliższa” jest definiowana jako długość najkrótszej krawędzi łączącej dwa klastry .

Rozwiązanie 2 jest podobne w duchu do tego, co opisujesz, ale szczegóły dotyczące śledzenia odległości między klastrami są nieco inne. Zachowujesz rzędy minimów macierzy odległości klastra, pozwalając ci zeskanować tę listę minimów wierszy w czasie liniowym, aby znaleźć globalne minimum, podczas gdy mój papier nakłada się na czworokąt na tej samej macierzy i śledzi minimum w każdym kwadratowy kwadrat. Twoja metoda jest prostsza, ale mniej elastyczna w przypadku niektórych innych dynamicznych problemów z najbliższymi parami (zależy to od tego, że połączenie dwóch klastrów powoduje zmniejszenie ich odległości do innych klastrów, co prawda w przypadku tego problemu, ale niekoniecznie w przypadku innych).

Jak napisałem w 2011 r. W artykule w Wikipedii na temat algorytmu łańcucha najbliższego sąsiada , algorytm ten można również wykorzystać do wykonania Kruskala w czasie . Jednak (w przeciwieństwie do innych aplikacji algorytmu łańcucha najbliższego sąsiada) nie uzyskuje się oszczędności miejsca, więc (podobnie jak metoda quadtree i twoja metoda) przestrzeń jest nadal . W przeciwieństwie do sortowania Prim +, można użyć tylko miejsca poza miejscem potrzebnym do przechowywania danych wejściowych.$O(n^2)$$O(n^2)$$O(n)$