Kiedy powinienem używać Kruskala w przeciwieństwie do Prim (i odwrotnie)?

Odpowiedzi:

200

Użyj algorytmu Prim, gdy masz wykres z dużą ilością krawędzi.

W przypadku wykresu z krawędziami V wierzchołków E algorytm Kruskala działa w czasie O (E log V), a algorytm Prim może działać w czasie zamortyzowanym O (E + V log V) , jeśli użyjesz sterty Fibonacciego .

Algorytm Prim jest znacznie szybszy w limicie, gdy masz naprawdę gęsty wykres z dużo większą liczbą krawędzi niż wierzchołków. Kruskal działa lepiej w typowych sytuacjach (rzadkie wykresy), ponieważ wykorzystuje prostsze struktury danych.

Todd Gamblin
źródło
8
Powiedziałbym „typowe sytuacje” zamiast przeciętnych. Myślę, że to niejasne określenie, na przykład jaki jest „średni rozmiar” tabeli mieszającej? brak pomysłu.
yairchu
2
@SplittingField: Uważam, że porównujesz jabłka i pomarańcze. Zamortyzowana analiza jest prostym sposobem uzyskania pomiaru funkcji (że tak powiem) --- to, czy jest to najgorszy czy średni przypadek, zależy od tego, co udowodnisz. W rzeczywistości (jak teraz patrzę) artykuł na wiki używa języka, który sugeruje, że jest on używany tylko do analizy najgorszych przypadków. Teraz użycie takiej analizy oznacza, że ​​nie można składać tak silnych obietnic dotyczących kosztu konkretnej operacji, ale do czasu wykonania algorytmu rzeczywiście stanie się to przez O (E + VlogV), nawet w najgorszym przypadku.
agorenst
10
Brzmi dobrze w teorii, ale założę się, że niewiele osób może wdrożyć stos Fibonacciego
Alexandru,
2
@tgamblin, w najgorszym przypadku mogą występować krawędzie C (V, 2). Czy zatem komplementarność czasowa algorytmu Prim nie sprowadza się do O (V ^ 2 + VlogV), tj. O (V ^ 2) w przypadku sterty fibonacciego?
Zielony goblin,
7
Jest jeszcze jeden ważny czynnik: wyjście Prims jest MST tylko wtedy, gdy wykres jest podłączony (wydaje mi się, że w innym przypadku nie ma sensu), ale wyjście Kruskala to lasy o minimalnym zasięgu (z pewnym wykorzystaniem).
Andrei I
100

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.wprowadź opis zdjęcia tutajwprowadź opis zdjęcia tutaj

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.

Snicolas
źródło
2
Nitpick: Ostatni „slajd” w każdym powinien brzmieć „powtarzaj, aż powstanie drzewo opinające”; dopiero w MST, co jest zadaniem rekurencyjnym - skąd mam wiedzieć, że jest minimalne - dlatego na początek podążam za Primem / Kruskalem!
OJFord,
@OllieFord Znalazłem ten wątek, ponieważ przeszukałem prostą ilustrację algorytmów Prim i Kruskal. Algorytmy gwarantują, że znajdziesz drzewo, a to drzewo jest MST. I wiesz, że znalazłeś drzewo, gdy masz dokładnie V-1 krawędzie.
mikedu95,
@ mikedu95 Masz rację, robiąc ten sam punkt, co mój poprzedni komentarz z innej perspektywy.
OJFord
Ale czy nie jest to warunek konieczny, aby wybrać tylko jedną wagę między wierzchołkami, nie możesz wybrać wagi 2 więcej niż raz z powyższego wykresu, musisz wybrać następną wagę np .: 3 @Snicolas
ani0904071
30

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.

malejpavouk
źródło
23

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.

Daniel C. Sobral
źródło
19

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²).

Ghiurutan Alexandru
źródło
Wydaje mi się, że Prim nigdy nie jest gorszy niż Kruskal pod względem szybkości. Ponieważ E powinno wynosić co najmniej V-1, istnieje drzewo opinające. Myślę, że powodem, dla którego możemy preferować Kruskala dla rzadkiego wykresu, jest to, że jego struktura danych jest zdecydowanie prosta.
Yu Gu
16

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

Prachar
źródło
5

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.

Jaskaran
źródło
3

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.

Leon Stenneth
źródło
2

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.

Sakshi
źródło
2

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.

Abhishek
źródło