Zastanawiało mnie, kiedy należy użyć Prim's algorithm, a kiedy Kruskal's znaleźć minimalne drzewo opinające? Obaj mają łatwą logikę, te same najgorsze przypadki, a jedyną różnicą jest implementacja, która może obejmować nieco inne struktury danych. Jaki jest decydujący czynnik?Kruskal kontra Prim
Użyj algorytmu Prim, gdy masz wykres z dużą liczbą krawędzi.
Na wykresie V wierzchołków E krawędzi, Algorytm Kruskala przebiega O (E log V) czasu i algorytm Prim może działać w O (E + log V V) zamortyzowany razem, jeśli używasz Fibonacci Heap.
Algorytm Prima jest znacznie szybszy w limicie, gdy mamy naprawdę gęsty wykres z wieloma krawędziami niż wierzchołkami. Kruskal radzi sobie lepiej w typowych sytuacjach (rozrzedzone wykresy), ponieważ używa prostszych struktur danych.
Kruskal może mieć lepszą wydajność, jeśli krawędzie mogą być sortowane w czasie liniowym lub są już posortowane.
Prim jest lepszy, jeśli liczba krawędzi do wierzchołków jest wysoka.
Najlepszy czas dla Kruskala to O (E logV). Dla Prim używających kupek Ful możemy uzyskać O (E + V lgV). Dlatego na gęstym wykresie Prim jest znacznie lepszy.
Wiem, że nie prosiłeś o to, ale jeśli masz więcej jednostek przetwarzania, powinieneś zawsze rozważyć Borůvka's algorithm, ponieważ może to być łatwo zrównoleglone - stąd ma on przewagę wydajności nad algorytmem Kruskala i Jarnika-Prim.
Jeśli zatrzymamy algorytmu w algorytmie środkowego Prim zawsze generuje podłączonego drzewo, ale Kruskala- z drugiej strony może dać odłączony drzewo lub las
Jednym ważnym zastosowaniem Algorytm Kruskala jest w pojedynczego łącza klastrów.
Rozważmy n wierzchołków i mamy kompletny wykres. Aby uzyskać ak klastrów tych n punktów. Rozpuść algorytm Kruskala na pierwszych krawędziach n- (k-1) posortowanego zestawu krawędzi. Otrzymasz k-skupisko wykres z maksymalnym odstępem.
Prim jest lepszy dla gęstszych wykresów, w tym również nie musimy zwracać uwagi na cykle, dodając przewagę, ponieważ mamy do czynienia głównie z węzłami. Prim jest szybszy niż Kruskal w przypadku złożonych wykresów.
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 z najtańszej krawędzi dodając kolejną najtańszą krawędź, pod warunkiem, że nie tworzy cyklu.
Algorytm Prima rozwinie rozwiązanie z losowego wierzchołka poprzez dodanie następnego najtańszego wierzchołka, wierzchołka, który nie jest aktualnie w rozwiązaniu, ale połączony z nim najtańszym brzegiem.
Tutaj załączony jest interesujący arkusz na ten temat.
Jeśli zaimplementujesz oba Kruskala i Prima, w ich optymalnej formie: przy znalezieniu związku i stosie finbonacci, zauważysz, że Kruskal jest łatwy do wdrożenia w porównaniu z Primem.
Prim jest trudniejszy w stosie Fibonacci, głównie dlatego, że trzeba utrzymywać tabelę księgowania, aby zapisać dwukierunkowe połączenie między węzłami wykresów a węzłami sterty. Z Union Find jest odwrotnie, struktura jest prosta i może nawet bezpośrednio produkować mst prawie bez dodatkowych kosztów.
Nitpick: Ostatni "slajd" w każdym powinien przeczytać "Powtarzaj, aż masz drzewo opinające"; nie do MST, co jest czymś w rodzaju zadania rekursywnego - skąd wiem, że to minimalne - dlatego na początku śledzę Prim/Kruskal's! – OJFord
@OllieFord Znalazłem ten wątek po przeszukaniu prostej ilustracji algorytmów Prim i Kruskal. Algorytmy gwarantują, że znajdziesz drzewo, a drzewo to MST. I wiesz, że znalazłeś drzewo, gdy masz * dokładnie * krawędzie "V-1". – mikedu95
@ mikedu95 Masz rację, robiąc to samo, co mój wcześniejszy komentarz pod innym kątem. – OJFord
W algorytmie kruskal mamy liczbę krawędzi i liczbę wierzchołków na danym wykresie, ale na każdej krawędzi mamy jakąś wartość lub wagę, w imieniu których możemy przygotować nowy wykres, który nie musi być cykliczny lub nie może być bliski strona Na przykład
wykres podobny do tego _____________ | | | | | | | __________ | | Podaj nazwę każdemu wierzchołkowi a, b, c, d, e, f.
Kruskala- czas złożoność najgorszy przypadek jest O (log E E), to dlatego, że trzeba posortować krawędzie. Prim czas złożoność najgorszy przypadek jest O (log E V) z priorytet kolejki lub nawet lepiej, O (log E + V V) z Fibonacciego Heap. Powinniśmy używać Kruskala, gdy wykres jest rzadki, tj. Mała liczba krawędzi, np. E = O (V), gdy krawędzie są już posortowane lub możemy je sortować w czasie liniowym. Powinniśmy używać Prim, gdy wykres jest gęsty, tj. Liczba krawędzi jest wysoka, jak E = O (V²).
Powiedziałbym "typowe sytuacje" zamiast średniej. Myślę, że jest to niejasne określenie, na przykład, jaki jest "średni rozmiar" tabeli hash? brak pomysłu. – yairchu
Nie zapomnij dodać, że stosy Prim + Fibonacciego dają amortyzowany czas działania, a nie najgorszy czas działania. – SplittingField
@SplittingField: Wierzę, że porównujesz jabłka i pomarańcze. Amortyzowana analiza jest w pewien sposób sposobem uzyskania pomiaru funkcji (że tak powiem) --- czy najgorszy przypadek, czy przeciętny przypadek zależy od tego, co udowodnisz. W rzeczywistości (kiedy już to sprawdzam), artykuł wiki używa języka, który sugeruje, że jego * jedyna * używana jest w najgorszym przypadku. Teraz użycie takiej analizy oznacza, że nie można składać tak dużych obietnic co do kosztu konkretnej operacji, ale do czasu, gdy algorytm zostanie wykonany, rzeczywiście będzie to O (E + VlogV), a nawet najgorszy przypadek . – agorenst