Algorytm Prima

Z Wikipedii

Niniejszy artykuł jest częścią cyklu teoria grafów.

Najważniejsze pojęcia
graf
podgraf
cykl
klika
stopień wierzchołka
dopełnienie grafu
obwód grafu
pokrycie wierzchołkowe
liczba chromatyczna
indeks chromatyczny
izomorfizm grafów
homeomorfizm grafów

więcej...

Wybrane klasy grafów
graf pełny
graf spójny
drzewo
graf dwudzielny
graf regularny
graf eulerowski
graf hamiltonowski
graf planarny

więcej...

Algorytmy grafowe
A*
Bellmana-Forda
Breadth-first search
Depth-first search
Dijkstry
Fleury'ego
Floyda-Warshalla
Johnsona
Kruskala
Prima
przeszukiwanie grafu
najbliższego sąsiada

Zagadnienia przedstawiane jako problemy grafowe
problem komiwojażera
problem chińskiego listonosza
problem kojarzenia małżeństw

Inne zagadnienia
kod Graya
diagram Hassego

edytuj ten szablon

Algorytm Prima lub algorytm Dijkstry-Prima – algorytm zachłanny wyznaczający tzw. minimalne drzewo rozpinające (MDR). Mając do dyspozycji graf nieskierowany i spójny, tzn. taki w którym krawędzie grafu nie mają ustalonego kierunku oraz dla każdych dwóch wierzchołków grafu istnieje droga pomiędzy nimi, algorytm oblicza o podzbiór E' zbioru krawędzi E, dla którego graf nadal pozostaje spójny, ale suma kosztów wszystkich krawędzi zbioru E' ma najmniejszą możliwą wartość.

Grafy zawierające dużo krawędzi, w których dwa te same wierzchołki połączone są np. trzema krawędziami lub pomiędzy dwoma wierzchołkami istnieje np. 5 różnych dróg długości 2, raczej nie są "lubiane" przez algorytmy i często przekształcenie takiego skomplikowanego grafu w graf mu równoważny pod względem zachowania możliwych połączeń przynosi znaczące korzyści.

[edytuj] Algorytm

Algorytm Prima wygląda tak:

utwórz drzewo zawierające jeden wierzchołek, dowolnie wybrany z grafu
utwórz zbiór zawierający wszystkie krawędzie grafu
powtarzaj, aż każda z pozostałych w zbiorze krawędzi będzie łączyła dwa wierzchołki drzewa:
- usuń ze zbioru krawędź o najmniejszej wadze, łączącą wierzchołek z drzewa z wierzchołkiem spoza drzewa
- dodaj tę krawędź do drzewa

Złożoność obliczeniowa (m to liczba krawędzi a n to liczba wierzchołków):

przy użyciu macierzy sąsiedztwa oraz tablicy: O(n^2)
przy użyciu kopca binarnego: O(m log(n))
przy użyciu kopca Fibonacciego O(m + n log(n)), co przy dużej gęstości grafu (takiej, że m jest ω(n log (n)) oznacza duże przyśpieszenie

[edytuj] Dowód poprawności

Niech dany będzie graf $\! G\ =\ <V,E>$ oraz dwa algorytmy: algorytm Prima, oraz niezachłanny i poprawny algorytm znajdowania MDR. Załóżmy, że drzewo spinające znalezione przez algorytm Prima nie jest minimalne.

Zakładamy, że drugi algorytm, podobnie jak algorytm Prima pobiera kolejne gałęzie grafu wejściowego, dołączając je do początkowo pustego drzewa wynikowego (odpowiednio $T p$ i $T o p t$ ). Załóżmy, że dla pierwszych i gałęzi algorytmy zadziałały tak samo, tj.

$\! e_0 e_1 \cdots e_i e\in T_p$

$\! e_0 e_1 \cdots e_i f\in T_{opt}$

krawędzie $\! f$ i $\! e$ są różne.

Niech $\! V^'$ oznacza zbiór wierzchołków grafu G połączonych krawędziami $\! e_0 e_1 \cdots e_i$ .

Ponieważ wybór e był niezachłanny, to waga e jest nie większa niż waga f.

$w(e)\le w(f)$

Niech

$\! T^'\ =\ T_{opt}\ +\ \{e\}\ -\ \{f\}$

Wtedy $\! T^'$ jest drzewem, ponieważ $\! T_{opt}$ jest drzewem, a krawędzie e i f mają tę własność, iż jeden z ich końców należy do $\! T_{opt}$ , a drugi prowadzi na jego zewnątrz.

A ponieważ

$\! w(e)-w(f)<0$ , to

$\! w(T^')\ =\ w(T_{opt})\ +\ w(e)\ -\ w(f)\ <\ w(T_{opt})$

co jest sprzeczne z wyborem $\! T_{opt}$ .

Podobne rozumowanie można przeprowadzić dla kolejnych dołączanych do drzew wynikowych krawędzi.

Wniosek – nie może istnieć drzewo spinające o sumie wag mniejszej, niż drzewo odnalezione algorytmem Prima – algorytm Prima zawsze odnajduje minimalne drzewo spinające.