prima

Algorytm Prima

Drugi algorytm wyznaczania minimalnego drzewa rozpinającego nosi nazwę algorytmu Prima i można go opisać w sposób następujący:

Wybieramy w grafie dowolny wierzchołek startowy.

Dopóki drzewo nie pokrywa całego grafu, znajdujemy krawędź o najniższym koszcie spośród wszystkich krawędzi prowadzących od wybranych już wierzchołków do wierzchołków jeszcze niewybranych. Znalezioną krawędź dodajemy do drzewa rozpinającego.

Przyjrzyjmy się bliżej pracy tego algorytmu:

3 Oto nasz graf ważony, dla którego mamy znaleźć minimalne drzewo rozpinające.

Wybieramy dowolny wierzchołek startowy, np. wierzchołek 0. Wierzchołek ten posiada trzy krawędzie biegnące do wierzchołków 1, 3 i 6. Spośród nich krawędź do wierzchołka 6 ma najmniejszą wagę i ją wybieramy dla drzewa rozpinającego.

Suma wag = 3

Spośród wszystkich krawędzi wychodzących z wierzchołków 0 i 6 (wierzchołki już wybrane) do wierzchołków jeszcze niewybranych krawędź 6-4 ma najmniejszą wagę i ją wybieramy dla drzewa rozpinającego.

Suma wag = 3 + 1=4

Teraz najmniejszą wagę ma krawędź 4-5. Dodajemy ją do drzewa rozpinającego. Suma wag = 3 + 1 + 2 = 6

Najmniejszą wagę ma krawędź 4-2. Dodajemy ją do drzewa rozpinającego. Suma wag = 3 + 1 + 2 + 4 = 10

Najmniejszą wagę ma krawędź 2-7. Dodajemy ją do drzewa rozpinającego. Suma wag = 3 + 1 + 2 + 4 + 3 = 13

Najmniejszą wagę ma krawędź 0-1. Dodajemy ją do drzewa rozpinającego. Suma wag = 3 + 1 + 2 + 4 + 3 + 5=18

Najmniejszą wagę ma krawędź 6-3. Dodajemy ją do drzewa rozpinającego. Suma wag = 3 + 1 + 2 + 4 + 3 + 5 + 8 = 26

Wszystkie wierzchołki znalazły się w drzewie rozpinającym. Zadanie wykonane.