algorytm.org

Algorytm Prima



Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Prima
Ocena użytkowników:***** / 86
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 09 sierpnia 2005 21:49

Zrozumienie algorytmu wymaga znajomości pojęć grafu oraz minimalnego drzewa rozpinającego
Algorytm ten jest oparty o metodę zachłanną.
Budowę minimalnego drzewa rozpinającego zaczynamy od dowolnego wierzchołka, np. od pierwszego. Dodajemy wierzchołek do drzewa a wszystkie krawędzie incydentne umieszczamy na posortowanej wg. wag liście. Następnie zdejmujemy z listy pierwszą krawędź (o najmniejszej wadze). Sprawdzamy, czy drugi wierzchołek tej krawędzi należy do tworzonego drzewa. Jeżeli tak, to nie ma sensu dodawać takiej krawędzi (bo oba jej wierzchołki znajdują sięw drzewie), porzucamy krawędź i pobieramy z listy następną. Jeżeli jednak wierzchołka nie ma w drzewie, to należy dodać krawędź do drzewa, by wierzchołek ten znalazł się w drzewie rozpinającym. Następnie dodajemy do posortowanej listy wszystkie krawędzie incydentne z dodanym wierzchołkiem i pobieramy z niej kolejny element.
Jednym zdaniem: zawsze dodajemy do drzewa krawędź o najmniejszej wadze, osiągalną (w przeciwieństwie do Kruskala) z jakiegoś wierzchołka tego drzewa.
Można zauważyć, że kluczową, z punktu widzenia wydajności algorytmu, czynnością jest zaimplementowanie listy posortowanej, gdyż po każdym dodaniu krawędzi, lista musi być nadal posortowana.

Przykład:

Przyjmijmy następującą notację: [ui, uj, w] oznacza krawędź łączącą wierzchołki (ui, uj) o wadze w.
Dany jest spójny graf nieskierowany:
Przebieg algorytmu:
algorytm Prima - krok 1 algorytm Prima - krok 2
Wybieramy wierzchołek a.
Tworzymy posortowaną listę
L={[a,e,1],[a,f,2],[a,b,4]}
Wybieramy krawędź (a,e).
Dodajemy nowe krawędzie:
L={[a,f,2],[e,b,2],[e,d,3],[a,b,4],[e,f,7]}
Wybieramy krawędź (a,f).
algorytm Prima - krok 3 algorytm Prima - krok 4
Krawędź [f,e,7] jest już na liście:
L={[e,b,2],[e,d,3],[a,b,4],[f,d,6],[e,f,7]}
Wybieramy krawędź (e,b).
Dodajemy krawędź (b,c):
L={[b,c,2],[e,d,3],[a,b,4],[f,d,6],[e,f,7]}
Wybieramy krawędź (b,c).
algorytm Prima - krok 5 algorytm Prima - krok 6
Dodajemy krawędź (c,d):
L={[e,d,3],[a,b,4],[f,d,6],[e,f,7],[c,d,8]}
Wybieramy krawędź (e,d).
Drzewo utworzone.

Suma wag krawędzi wchodzących w skład drzewa wynosi 10.
Zobacz też: Algorytm Kruskala.


Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Marcin WalewskiC/C++
.cpp
.cpp
***** / 28
Michał KnasieckiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 10
mephistoJavaWersja leniwa algorytmu
.java
.java
***** / 4
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 16 sierpnia 2012 20:25
Komentarze
photo
-25 # Kamil 2009-10-17 00:12
Ten algorytm nie jest zbyt dobry, bo co jeśli w podanym powyżej grafie zamienimy wagi krawędzi [a,b] i [e,d], czyli wtedy wynosić będą: [a,b,3], [e,d,4] to w tym przypadku algorytm Prima się by \'wysypał\' i nie zbudowałby minimalnego drzewa rozpinającego.

Pozdrawiam,
Kamil
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+23 # Krolik 2009-10-28 08:26
Kamil, powiedz w jaki sposób udało Ci się stwierdzić, że po zamianie wag krawędzi, o których mówiłeś, algorytm Prima nie daje MST?
Może zgłoś to do jakiejś organizacji, bo właśnie chcesz wykazać, że stosowany od lat algorytm, którego poprawne działanie UDOWODNIONO, nie działa. Może Ci pomnik postawią.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-10 # Franek 2009-12-30 15:11
Ponieważ:

prim(0); // start at vertex 0

cout
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-3 # lobo 2010-04-20 13:17
Jeżeli dokonasz takiej zmiany to nadal będzie działało tylko suma wag będzie większa tzn. najpierw do a przyłączy się e, (1) następnie dołączy f (1+2), kolejne będzie b (1+2+2), c (1+2+2+2), d(1+2+2+2+4) czyli suma będzie 11 nadal najmniejsza możliwa.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # JarekXXX 2011-06-15 19:35
"Następnie zdejmujemy z listy pierwszą krawędź (o najmniejszej wadze). Sprawdzamy, czy drugi wierzchołek tej krawędzi należy do tworzonego drzewa. Jeżeli tak, to nie ma sensu dodawać takiej krawędzi (bo oba jej wierzchołki znajdują sięw drzewie), porzucamy krawędź i pobieramy z listy następną." Dlatego się nie wysypie xD
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-2 # Borneq 2011-12-04 23:56
Listę krawędzi można trzymać w kopcu a najlepiej w kopcu Fibonacciego
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz