Prim-algoritmus

A Wikipédiából, a szabad enciklopédiából

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.

Az algoritmus leírása[szerkesztés | forrásszöveg szerkesztése]

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á.

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 {x}; Y:= Y-{y}
06 Eredmény: az (A,F) fa

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.

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.

Ex prim.JPG Ex prim 1.JPG 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ú.

Ex prim.JPG Ex prim 2.JPG 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ú.

Ex prim.JPG Ex prim 3.JPG 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ú.

Ex prim.JPG Ex prim 4.JPG 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!

Ex prim.JPG Ex prim 5.JPG 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ú.

Ex prim.JPG Ex prim 6.JPG 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ú.

Ex prim.JPG Ex prim 7.JPG 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-
Ex prim.JPG Ex prim 8.JPG 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[szerkesztés | forrásszöveg szerkesztése]

Helyessége[szerkesztés | forrásszöveg szerkesztése]

A helyesség bizonyítása Andrásfai Béla[1] ö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.

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

  1. Andrásfai Béla: Ismerkedés a gráfelmélettel, Tankönyvkiadó, Budapest, 1971,

Források[szerkesztés | forrásszöveg szerkesztése]

  • 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.

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]

További információk[szerkesztés | forrásszöveg szerkesztése]