Różnica między Kruskal a Prim

Kruskal vs Prim

W informatyce algorytmy Prim i Kruskala są chciwym algorytmem, który znajduje minimalne drzewo rozpinające dla połączonego ważonego niekierowanego wykresu. Drzewo opinające jest podgrafem wykresu, tak że każdy węzeł wykresu jest połączony ścieżką, która jest drzewem. Każde drzewo opinające ma wagę, a minimalna możliwa waga / koszt wszystkich drzew opinających to minimalne drzewo opinające (MST).

Więcej informacji o algorytmie Prim

Algorytm został opracowany przez czeskiego matematyka Vojtěcha Jarníka w 1930 r., A następnie niezależnie przez informatyka Roberta C. Prim w 1957 r. Został ponownie odkryty przez Edsger Dijkstra w 1959 r. Algorytm można sformułować 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ą dwa lub więcej minimów)

3. Powtarzaj krok 2, aż do drzewa doda się krawędzie n-1.

W tej metodzie drzewo zaczyna się od pojedynczego dowolnego węzła i rozwija się od tego węzła z każdym kolejnym cyklem. Dlatego, aby algorytm działał poprawnie, wykres musi być połączonym wykresem. Podstawowa postać algorytmu Prim ma złożoność czasową O (V²⁾).

Więcej informacji o algorytmie Kruskala

Algorytm opracowany przez Josepha Kruskala pojawił się w postępowaniu American Mathematical Society w 1956 r. 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 masie całego wykresu, dodaj do drzewa i usuń z wykresu.

2. Z pozostałych wybierz najmniej ważoną krawędź w sposób, który nie tworzy cyklu. Dodaj krawędź do drzewa i usuń z wykresu. (Wybierz dowolne, jeśli istnieją dwa lub więcej minimów)

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 wykres nie musi być łączony. Algorytm Kruskala ma złożoność czasową O (logV)

Jaka jest różnica między algorytmem Kruskala a Primem?

• Algorytm Prim inicjuje się za pomocą węzła, podczas gdy algorytm Kruskala inicjuje za pomocą krawędzi.

• Algorytmy Prim 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 Prim, wykres musi być grafem połączonym, podczas gdy Kruskal może również działać na grafach rozłączonych.

• Algorytm Prim ma złożoność czasową O (V²⁾), a złożoność czasowa Kruskala wynosi O (logV).