Różnica Między Kruskalem A Prim

2024 Autor: Mildred Bawerman | [email protected]. Ostatnio zmodyfikowany: 2023-12-16 08:41

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

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 ²), a złożoność czasową Kruskala wynosi O (logV).