Kruskal vs Prim
W informatyce algorytmy Prima i Kruskala są chciwym algorytmem, który znajduje minimalne drzewo rozpinające dla połączonego ważonego grafu niekierowanego. Drzewo rozpinające to podgraf wykresu, w którym każdy węzeł jest połączony ścieżką, która jest drzewem. Każde drzewo opinające ma swoją wagę, a minimalna możliwa waga / koszt wszystkich drzew rozpinających to minimalne drzewo opinające (MST).
Więcej o algorytmie Prim
Algorytm został opracowany przez czeskiego matematyka Vojtěcha Jarníka w 1930 r., A później niezależnie przez informatyka Roberta C. Prima w 1957 r. Odkrył go ponownie Edsger Dijkstra w 1959 r. Algorytm można określić 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óre 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 dodania n-1 krawędzi do drzewa.
W tej metodzie drzewo zaczyna się od pojedynczego dowolnego węzła i rozwija się od tego węzła w każdym cyklu. Dlatego, aby algorytm działał poprawnie, wykres musi być grafem połączonym. Podstawowa postać algorytmu Prima ma złożoność czasową O (V 2).
Więcej o algorytmie Kruskala
Algorytm opracowany przez Josepha Kruskala pojawił się w pracach American Mathematical Society 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 go do drzewa i usuń z wykresu.
2. Z pozostałych wybierz najmniej obciążoną krawędź, tak aby nie tworzyła cyklu. Dodaj krawędź do drzewa i usuń z wykresu. (Wybierz dowolne, jeśli istnieją co najmniej dwa minimum)
3. Powtórz proces z 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ć łączony. Algorytm Kruskala ma złożoność czasową O (logV)
Jaka jest różnica między algorytmem Kruskala i Prim?
• Algorytm Prima inicjuje się węzłem, podczas gdy algorytm Kruskala inicjuje 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 położenie krawędzi nie jest oparte na ostatnim kroku.
• W algorytmie Prima graf musi być grafem połączonym, podczas gdy wykres Kruskala może również działać na grafach odłączonych.
• Algorytm Prima ma złożoność czasową O (V 2), a złożoność czasową Kruskala wynosi O (logV).
