Prim-algoritmus

A Prim-algoritmus egy összefüggő súlyozott gráf minimális feszítőfáját határozza meg mohó stratégia segítségével. Működési elve, hogy csúcsonként haladva építi fel a fát, egy tetszőleges csúcsból kiindulva és minden egyes lépésben a lehető legolcsóbb élt keresi meg egy következő csúcshoz. Az algoritmust először Vojtěch Jarník írta le 1930-ban, de ez az eredmény ismeretlen maradt. Tőle függetlenül Robert C. Prim 1957-ben és Edsger Dijkstra 1959-ben újra felfedezték. Ezért az algoritmust nevezik még DJP-algoritmusnak, Jarník-algoritmusnak vagy Prim−Jarník-algoritmusnak is.

További ehhez hasonló algoritmus még a Kruskal-algoritmus és a Boruzvka-algoritmus. Ezek az algoritmusok megkeresik egy feltehetőleg nem összefüggő gráf minimális feszítő erdejét. Ezzel szemben a Prim-algoritmus egyszerű verziója egy összefüggő gráfban találja meg a minimális feszítőfát. Azonban a Prim-algoritmus alkalmazása a gráf különböző kapcsolódási pontjain szintén megtalálja a minimális feszítőerdőt. Ami a bonyolultságot illeti, mindhárom algoritmus egyformán gyors sűrű gráfokban, de lassabb más kifinomultabb algoritmusoknál. Az elég sűrű gráfok esetén a Prim-algoritmus lineáris idő alatt lefuttatható, azonosan vagy túlteljesítve más algoritmusok időbeli megkötéseit.

Az algoritmus leírása

Az algoritmus lépésenként építi fel a minimális feszítőfát, minden lépésben egy csúcsot adva hozzá.

Prim-algoritmus szemléltetése euklideszi távolságon alapulva

Az algoritmus lépései a következők:

• Válasszuk ki a gráf egy tetszőleges csúcsát, legyen ez egy egycsúcsú fa.
• Ameddig van a gráfnak olyan csúcsa, amelyik nincs benne a fában, végezzük el a következőket:

• Válasszuk ki a fa csúcsai és a gráf többi csúcsa között futó élek közül a legkisebb súlyút.
• A kiválasztott él nem fabeli csúcsát tegyük át a fába az éllel együtt.

Formálisabban:

00 Jelöljük V-vel a gráf csúcsainak halmazát.
 Jelöljük a feszítőfa csúcsainak halmazát X-szel, éleinek halmazát pedig F-fel.
01 Válasszunk ki tetszőlegesen egy csúcsot, legyen ez v.
02 X:={v}; Y:= V-X; F:=üres
03 while X ≠ V do
04 legyen {x,y}, ahol x $\in$ X, y $\in$ Y, a legkisebb súlyú él az
 X és Y közötti élek közül
05 F:=F $\cup$ {(x,y)}; X:= X $\cup$ {y}; Y:= Y-{y}
06 Eredmény: az (X,F) fa

Példa

A következő példában, lépésenként bemutatjuk az algoritmust. A táblázat második oszlopában az X és Y csúcshalmazokat egy szaggatott függőleges vonallal választjuk el, és csak a fa, valamint az X és Y közötti éleket jelöljük a megfelelő súlyokkal. Az első oszlopban mindig az eredeti gráf szerepel, hogy könnyen ellenőrizhessük az X és Y közötti éleket.

		Kiválasztjuk az a csúcsot, kezdetben ez a fa. Kiválasztjuk a hozzá illeszkedő élek közül a legkisebb súlyút. Ez a c csúcs. Most az a és c csúcs, valamint az ezeket összekötő él képezi az új fát. A fa és a gráf többi csúcsa közötti élek közül a {c,h} él a legkisebb súlyú.
		A h csúcs és a {c,h} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {h,g} él a legkisebb súlyú.
		A g csúcs és a {h,g} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {g,e} él a legkisebb súlyú.
		Az e csúcs és a {g,e} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {c,d} és {h,d} élek mindegyike legkisebb súlyú. Bármelyiket választhatjuk. Válasszuk a {c,d} élt!
		A d csúcs és a {c,d} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül a {c,b} él a legkisebb súlyú.
		A b csúcs és a {c,b} él átkerül a fába. A fa és a gráf többi csúcsa közötti élek közül az {a,f} él a legkisebb súlyú.
		Az f csúcs és az {a,f} él átkerül a fába, amely feszítőfa, mivel a gráf minden csúcsát tartalmazza.
		Az eredmény az eredeti gráf csúcselrendeződése szerint.

Amennyiben minden lépésben csupán egy legkisebb súlyú él van, a megoldás egyértelmű. Különben több minimális értékű feszítőfa létezhet.

Bonyolultsága

A Prim-algoritmus bonyolultsága az gráfnál alkalmazott adatszerkezettől és az élek súly szerinti rendezettségétől függ, ami az elsőbbségi sor segítségével lehetséges. Az alábbi táblázat a gyakori választásokat mutatja be:

Minimális élű adatszerkezet	Teljes bonyolultság
Szomszédsági mátrix, keresés	O(|V|2)
Bináris kupac és szomszédsági lista	O((|V| +|E|) log |V|) = O(|E| log |V| )
Fibonacci kupac és szomszédsági lista	O(|E| +|V|log |V|)

A Prim-algoritmus egy egyszerű megvalósítása, ami lineárisan nézi végig a súlyok listáját, hogy megtalálja a minimális hozzáadandó élt, O(|V|²) futási időbe telik. Ez a futási idő azonban jelentősen javítható, ha kupacokat használunk a minimális súlyú élek megtalálására a belső hurokban.

Az első továbbfejlesztett verziója kupacot használ, hogy eltárolja a súly szerint rendezett bemeneti gráf összes élét. Azonban élek helyett a csúcsok eltárolása még tovább fejlesztheti az algoritmust. A kupac a csúcsokat azon legkisebb él súlyok szerint rendezi,melyek tetszőleges a csúcsokkal kötik össze őket, a részlegesen felépített minimális feszítőfában (MFF) (vagy végtelen, ha nem létezik ilyen él). Mindig, amikor egy v csúcs kiválasztásra kerül és hozzáadódik a minimális feszítőfához, egy kulcs-csökkentő művelet lefut minden olyan a feszítőfán kívül eső w csúcson, ahol v össze van kötve w –vel és a kulcs az ezt megelőző érték minimumára van állítva és a élek költsége (v,w).

Egy egyszerű bináris kupac adatszerkezetet használva a Prim-algoritmus most már O(|E| log |V| ) idő alatt fut le, ahol |E| az élek száma |V| pedig a csúcsok száma. Az ennél precízebb Fibonacci-kupacot használva a bonyolultság O(|E| +|V|log |V|) –ra redukálható, ami aszimptotikusan gyorsabb, ha a gráf elég sűrű. Az ennél is sűrűbb gráfok esetén (legalább |V|^c éllel, ahol c>1), a Prim-algoritmus lineáris idejű futása még egyszerűbb, a Fibonacci helyett egy d-kupac (speciális bináris kupac) használatával.

Helyessége

A helyesség bizonyítása Andrásfai Béla ötletén alapszik. Könnyű belátni, hogy az algoritmus eredményeként mindegyik csúcshoz illeszkedő élek közül a legkisebb súlyú biztos benne van a megoldásban. Tehát színezzük ki pirossal az eredeti gráf azon éleit, amelyek az egyes csúcsokhoz illeszkedők közül a legkisebb súlyúak. Ha a piros élek egy feszítőfa élei, akkor ez a fa nyilván minimális. Ha az eredmény nem feszítőfa, akkor a piros élek több fa élei. Vonjuk össze ezen fák mindegyikét egy-egy csúcsba. Az így kapott fára alkalmazzuk újra az élek kifestését a fenti módon. Amikor a színezés befejeződik, az eredeti gráf ilyen módon kiszínezett élei egy feszítő fa élei lesznek, és pont azok, amelyeket az algoritmus is kiválaszt. Ez a fa természetesen minimális feszítőfa.

Formálisabban:

Legyen P egy összefüggő, súlyozott gráf. A Prim-algoritmus minden lépésében találnunk kell egy élt, ami egy részgráf egy élét a részgráfon kívüli éllel köti össze. Mivel P összefüggő, minden csúcshoz lesz út. Az algoritmus kimenetele legyen az Y fa. Legyen Y1 a gráf minimális feszítőfája. Ha Y1 = Y, akkor Y a minimális feszítőfa. Egyébként, legyen e az első hozzáadott él az Y fa elkészítésekor, ami nincs benne az Y1 fában és V az olyan élek által összekötött csúcsok halmaza melyek e előtt lettek hozzáadva. Ekkor az e él egyik végpontja eleme a V halmaznak , a másik nem. Mivel Y1, a P gráf egy feszítőfája, van Y1-nek olyan útja, ami a két végpontot köti össze. Ahogy bejárjuk az utat, találkoznunk kell egy olyan f éllel, ami egy V-beli csúcsot egy nem V-belivel köt össze. Annál a lépésnél, amikor az e él hozzá lett adva az Y fához, f–et is hozzá lehetett volna adni, méghozzá e helyett, ha a súlya kisebb mint e-nek, de mivel f-et nem adtuk hozzá, levonhatjuk azt a következtetést, hogy

w(f) ≥ w (e).

Legyen Y2 az a fa, amit úgy kaptunk, hogy eltávolítottuk az f élt és hozzáadtuk e-t az Y1 fához. Könnyen belátható, hogy Y1 összefüggő, ugyanannyi éle van, mint Y1-nek és az élek összsúlya nem nagyobb Y1 élei összsúlyának, így hát Y2 is egy minimális feszítőfája a P gráfnak, tartalmazza az e élt és minden más élt ami e előtt lett hozzáadva a V halmaz készítése során. A fenti lépéseket véges sokszor alkalmazva megkapjuk az Y minimális feszítőfát.

Párhuzamos algoritmusok

A Prim-algoritmus fő hurka eredendően szekvenciális, tehát nem párhuzamosítható. A belső hurok, amely meghatározza a következő minimális súlyú élt, ami nem alkot kört, párhuzamosítható úgy, hogy a csúcsokat és az éleket megosztja a rendelkezésre álló processzorok között. A következő pszeudokód ezt szemlélteti.

1. Rendeljünk hozzá minden egyes Pi processzorhoz egy Vi halmazt az egymást követő csúcsok halmazából, melyek hossza ${\tfrac {|V|}{|P|}}$.

2. Hozzuk létre a C, E , F és Q halmazokat, mint a szekvenciális algoritmusban, és osszuk fel C-t, E-t, valamint a gráfot az összes processzor között, mégpedig úgy, hogy minden processzor tárolja a bejövő éleket a csúcsok halmazában.

3. Ismételjük a következő lépéseket addig, amíg Q nem üres. a, Minden processzor: keresse meg a vi csúcsot, aminek a Ci[vi] (helyi megoldás) értéke minimális. b, Csökkentsük ezeket az értékeket (minimumcsökkentés), hogy megtaláljuk azt a v csúcsot, amelyre a lehető legkisebb a C[v] érték (globális megoldás). c, Adjuk meg a kiválasztott csomópontot minden processzornak. d, Adjuk hozzá v-t az F halmazhoz, és ha E[v] nem az indikátorérték, adjuk hozzá E[v]-t is az F halmazhoz. e, Minden processzoron frissítsük Ci és Ei halmazokat.

4. Térjünk vissza F-fel.

Ez az algoritmus általában megosztott gépeken, valamint megosztott memóriákat használó eszközökön is megvalósítható. Grafikus feldolgozó egységeken (GPU) is futtatták már. A futási idő $O({\tfrac {|V|^{2}}{|P|}})+O(|V|\log |P|)$, feltételezve, hogy a redukciós és a sugárzási műveletek végrehajthatók $O(\log |P|)$ időn belül. A Prim egy olyan változata is létezik már, amelyben a Prim szekvenciális algoritmust párhuzamosan hajtjuk végre, különböző csúcsoktól indulva, olyan eszközökön, melyek megosztják a memóriakapacitásukat. Meg kell azonban jegyezni, hogy léteznek kifinomultabb algoritmusok az megosztott minimális feszítőfa probléma hatékonyabb megoldására.

Jegyzetek

Dijkstra algoritmusa, egy nagyon hasonló algoritmus a legrövidebb út problémájához.

Források

• V. Jarník: O jistém problému minimálním (Egy bizonyos minimális problémáról), Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57–63. (cseh nyelven)
• R. C. Prim: Shortest connection networks and some generalizations, Bell System Technical Journal, 36 (1957), pp. 1389–1401. Online hozzáférés
• D. Cheriton, R. E. Tarjan: Finding minimum spanning trees, SIAM Journal on Computing, 5 (Dec. 1976), pp. 724–741
• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Új algoritmusok, Scolar Kiadó, 2003.
• Rosen, Kenneth (2011) Discrete Mathematics and Its Applications, (7th ed.), McGraw-Hill Science, p. 798
• Wang, Wei; Huang, Yongzhong; Guo, Shaozhong (2011). "Design and Implementation of GPU-Based Prim's Algorithm". International Journal of Modern Education and Computer Science 3.4.
• Setia, Rohit (2009). "A new parallel algorithm for minimum spanning tree problem". Proc. International Conference on High Performance Computing (HiPC).

Kapcsolódó szócikkek

• Minimális feszítőfa
• Kruskal-algoritmus

További információk

• Animáció
• Java applet