Zastanawiałem się, kiedy należy użyć algorytmu Prim, a kiedy Kruskala znaleźć minimalne drzewo rozpinające? Oba mają łatwą logikę, te same najgorsze przypadki, a jedyną różnicą jest implementacja, która może obejmować nieco inne struktury danych. Więc jaki jest decydujący czynnik?
193
Znalazłem bardzo ładny wątek w sieci, który wyjaśnia różnicę w bardzo prosty sposób: http://www.thestudentroom.co.uk/showthread.php?t=232168 .
Algorytm Kruskala rozwinie rozwiązanie od najtańszej krawędzi, dodając kolejną najtańszą krawędź, pod warunkiem, że nie utworzy cyklu.
Algorytm Prim wyhoduje rozwiązanie z losowego wierzchołka, dodając następny najtańszy wierzchołek, wierzchołek, który nie jest obecnie w rozwiązaniu, ale jest połączony z nim najtańszą krawędzią.
W załączeniu znajduje się ciekawy arkusz na ten temat.
Jeśli zaimplementujesz zarówno Kruskal, jak i Prim, w ich optymalnej formie: odpowiednio z znalezieniem związku i stertą finbonacci, zauważysz, jak Kruskal jest łatwy do wdrożenia w porównaniu z Prim.
Prim jest trudniejszy z kupą Fibonacciego głównie dlatego, że musisz utrzymywać tabelę księgową, aby rejestrować dwukierunkowe połączenie między węzłami grafowymi i węzłami sterty. Z Union Find jest odwrotnie, struktura jest prosta i może nawet produkować bezpośrednio najwięcej bez prawie żadnych dodatkowych kosztów.
źródło
V-1
krawędzie.Wiem, że o to nie prosiłeś, ale jeśli masz więcej jednostek przetwarzających, zawsze powinieneś rozważyć algorytm Borůvki , ponieważ może on być łatwo zrównoleglony - stąd ma przewagę wydajności nad algorytmem Kruskala i Jarníka-Prim.
źródło
Kruskal może mieć lepszą wydajność, jeśli krawędzie można posortować w czasie liniowym lub są już posortowane.
Prim jest lepszy, jeśli liczba krawędzi do wierzchołków jest wysoka.
źródło
Najgorszym przypadkiem złożoności czasu Kruskala jest O (E log E) , ponieważ musimy uporządkować krawędzie. Prim czas złożoność najgorszy przypadek jest O (log E V) z priorytetu kolejki , a nawet lepiej, O (log E + V V) z Fibonacciego Heap . Powinniśmy użyć Kruskala, gdy wykres jest rzadki, co oznacza niewielką liczbę krawędzi, np. E = O (V), kiedy krawędzie są już posortowane lub jeśli możemy je posortować w czasie liniowym. Powinniśmy używać Prim, gdy wykres jest gęsty, tj. Liczba krawędzi jest wysoka, jak E = O (V²).
źródło
Jeśli zatrzymamy algorytm w algorytmie środkowego primu, zawsze generuje ono połączone drzewo, ale z drugiej strony kruskal może dać rozłączone drzewo lub las
źródło
Jednym z ważnych zastosowań algorytmu Kruskala jest klastrowanie pojedynczego łącza .
Rozważ n wierzchołków, a otrzymasz kompletny wykres. Aby uzyskać klastry ak tych n punktów. Uruchom algorytm Kruskala na pierwszych n- (k-1) krawędziach posortowanego zestawu krawędzi. Otrzymasz k-skupisko wykresu z maksimum rozstaw.
źródło
Najlepszy czas na Kruskala to O (E logV). Dla Prim za pomocą hałd możemy uzyskać O (E + V lgV). Dlatego na gęstym wykresie Prim jest znacznie lepszy.
źródło
Prim's jest lepszy dla bardziej gęstych wykresów, a przy tym nie musimy również zwracać dużej uwagi na cykle, dodając krawędź, ponieważ mamy do czynienia głównie z węzłami. Prim jest szybszy niż Kruskala w przypadku złożonych wykresów.
źródło
W algorytmie kruskala mamy liczbę krawędzi i liczbę wierzchołków na danym wykresie, ale na każdej krawędzi mamy pewną wartość lub wagę, w imieniu której możemy przygotować nowy wykres, który nie musi być cykliczny lub nie może być zamknięty z żadnej strony Na przykład
wykres taki jak ten _____________ | | | | | | | __________ | | Nadaj nazwę dowolnemu wierzchołkowi a, b, c, d, e, f.
źródło