Kruskal kontra Prim
W informatyce algorytmy Prima i Kruskala to zachłanny algorytm, który znajduje minimalne drzewo rozpinające dla połączonego ważonego grafu nieskierowanego. Drzewo opinające to podgraf grafu, w którym każdy węzeł grafu jest połączony ścieżką, którą jest drzewo. Każde drzewo opinające ma swoją wagę, a minimalna możliwa waga/koszt wszystkich drzew opinających to minimalne drzewo opinające (MST).
Więcej o algorytmie Prim
Algorytm został opracowany przez czeskiego matematyka Vojtěcha Jarníka w 1930 roku, a później niezależnie przez informatyka Roberta C. Prima w 1957 roku. Został ponownie odkryty przez Edsgera Dijkstrę w 1959 roku. Algorytm można przedstawić w trzech kluczowych krokach;
Biorąc pod uwagę połączony wykres z n węzłami i odpowiednią wagą każdej krawędzi, 1. Wybierz dowolny węzeł z wykresu i dodaj go do drzewa T (który będzie pierwszym węzłem)
2. Rozważ wagi każdej krawędzi połączonej z węzłami w drzewie i wybierz minimum. Dodaj krawędź i węzeł na drugim końcu drzewa T i usuń krawędź z wykresu. (Wybierz dowolne, jeśli istnieją co najmniej dwa minimum)
3. Powtarzaj krok 2, aż do drzewa zostanie dodanych n-1 krawędzi.
W tej metodzie drzewo zaczyna się od jednego dowolnego węzła i rozwija się od tego węzła w każdym cyklu. Dlatego, aby algorytm działał poprawnie, graf musi być grafem połączonym. Podstawowa forma algorytmu Prim ma złożoność czasową O(V2).
Więcej o algorytmie Kruskala
Algorytm opracowany przez Josepha Kruskala pojawił się w postępowaniu Amerykańskiego Towarzystwa Matematycznego w 1956 roku. Algorytm Kruskala można również wyrazić w trzech prostych krokach.
Biorąc pod uwagę wykres z n węzłami i odpowiednią wagą każdej krawędzi, 1. Wybierz łuk o najmniejszej wadze całego wykresu, dodaj do drzewa i usuń z wykresu.
2. Z pozostałych wybierz najmniej ważoną krawędź, w sposób nie tworzący cyklu. Dodaj krawędź do drzewa i usuń z wykresu. (Wybierz dowolne, jeśli istnieją co najmniej dwa minimum)
3. Powtórz proces w kroku 2.
W tej metodzie algorytm rozpoczyna się od najmniej ważonej krawędzi i kontynuuje wybieranie każdej krawędzi w każdym cyklu. Dlatego w algorytmie graf nie musi być połączony. Algorytm Kruskala ma złożoność czasową O(logV)
Jaka jest różnica między algorytmem Kruskala i Prim?
• Algorytm Prima inicjuje się od węzła, podczas gdy algorytm Kruskala zaczyna się od krawędzi.
• Algorytmy Prima rozciągają się od jednego węzła do drugiego, podczas gdy algorytm Kruskala wybiera krawędzie w taki sposób, że pozycja krawędzi nie jest oparta na ostatnim kroku.
• W algorytmie prim graf musi być grafem połączonym, podczas gdy Kruskala może działać również na grafach rozłącznych.
• Algorytm Prima ma złożoność czasową O(V2), a złożoność czasowa Kruskala to O(logV).
