Borůvka-algoritmus

A Wikipédiából, a szabad enciklopédiából
A Boruvka-algoritmus animációja

A Borůvka-algoritmus egy mohó algoritmus mely alkalmas egy minimális feszítőfa megkeresésére egy olyan gráfban, amelyben az összes él különbözik, vagy egy minimális feszítőerdő megtalálására olyan gráf esetén, amely nem összefüggő.

Elsőként 1926-ban Otakar Borůvka tette közzé mint egy hatékony módszert Morvaország villamos hálózatának kiépítéséhez.[1][2][3] Az algoritmust Choquet fedezte fel újra 1938-ban;[4] majd Florek, Łukasiewicz, Perkal, Steinhaus és Zubrzycki 1951-ben;[5] és újra Georges Sollin 1965-ben.[6] Ezt az algoritmust gyakran nevezik Sollin-algoritmusnak, különösen a párhuzamos számítástechnika irodalmában.

Az algoritmus először megkeresi a gráf minden csúcsához tartozó legkisebb súlyú élt, és hozzáadja ezeket az éleket az erdőhöz. Ezt egy hasonló eljárás követi, amikor megkeresi a legkisebb súlyú éleket az összes eddig épített fán összehasonlítva egy másik fával, és hozzáadja ezeket az éleket az erdőhöz. Ennek a folyamatnak minden egyes ismétlése csökkenti a fák számát a gráf minden egyes összekötött komponensén belül a korábbi érték legfeljebb felére, tehát logaritmikusan sok ismétlés után a folyamat befejeződik. Amikor ez megtörténik, a hozzáadott élek halmaza egy minimum feszítőerdőt képez.

Pszeudokód[szerkesztés]

Az egyes csúcsok vagy csatlakoztatott csúcsok halmaza egy "Összefüggő komponens", a Borůvka algoritmus pszeudókója: 

 algoritmus Borůvka is
  input: egy G gráf, amelynek élei különböző súlyokkal rendelkeznek.
  output: F a G minimális feszítőerdője.

  Inicializálja az F erdőt egy csúcsú fák halmazává, egyet a gráf minden csúcsához.

  amíg F-nek egynél több komponense van addig
    Keresse meg az F kapcsolt komponenseit, és jelölje meg G minden egyes csúcsát a  komponense alapján
    Inicializálja az egyes komponensek legalacsonyabb élét a "Nincs" értékre.
    minden él uv G-nek addig
      ha az u és a v eltérő komponens címkék:
        ha az uv alacsonyabb, mint az u komponensének legalacsonyabb éle, akkor
          Állítsa uv-t az u komponensének legalacsonyabb élévé
        ha az uv alacsonyabb, mint az v komponensének legalacsonyabb éle, akkor
          Állítsa uv-t az v komponensének legalacsonyabb élévé
    minden egyes komponens, amelynek legalacsonyabb éle nem „Nincs” amíg
      Adja hozzá a legalacsonyabb élét F-hez

Ha az éleknek nincs eltérő súlyuk, akkor alkalmazható egy következetes kötési szabály (pl. A kötés megszakítása az élek objektumazonosítói szerint). Lehetséges optimalizálás (az elemzéshez nem szükséges) hogy eltávolítunk a G-ből minden olyan élt, amelyről kiderül, hogy két csúcsot összeköt egymással ugyanabban az összetevőben.

Bonyolultság[szerkesztés]

A Borůvka-algoritmus ábrázolható úgy, hogy vesszük a külső hurok O (log V ) iterációit, egészen a megállásig, és ezért az O időben ( E log V ) fut, ahol E az élek száma, és V a csúcsok száma a G-ben. Síkbarajzolható gráfoknál és általánosságban a minor gráf műveletekkel bezárt gráfcsaládok esetében lineáris időben futtatható úgy, hogy az algoritmus minden egyes fázisa után az összes komponens párból a legalacsonyabb élek kivételével az összes élt eltávolítjuk.[7]

Példa[szerkesztés]

Kép komponensek Leírás
{A}
{B}
{C}
{D}
{E}
{F}
{G} 		Ez az eredeti súlyozott gráfunk. Az élek mellett szereplő számok jelölik a súlyukat. Kezdetben minden csúcs önmagában egy komponens (kék körök).
{A, B, D, F}
{C, E, G} 		A külső hurok első iterációjában minden komponens legkisebb súlyú élét vesszük. Egyes éleket duplán választunk ki (AD, CE). Két elem marad meg.
{A, B, C, D, E, F, G} A második és utolsó iterációban a két megmaradt komponens legkisebb súlyú élét választjuk ki. Ezek jelen esetben ugyanazok az élek. Az egyik elem megmarad és készen vagyunk. A BD élt nem vesszük figyelembe, mivel mindkét végpont ugyanabban a komponensben van.

Egyéb algoritmusok[szerkesztés]

A probléma megoldására használható egyéb algoritmusok közé tartozik a Prim-algoritmus és a Kruskal-algoritmus. Gyors párhuzamos algoritmusok úgy állíthatók elő, hogy a Prim-algoritmust kombinálják a Borůvka-algoritmussal.[8]

Gyorsabb, randomizált minimális feszítőfa algoritmus, amely részben Borůvka algoritmusán alapul, Karger, Klein és Tarjan nevéhez köthető O(E) várható futási idővel.[9] A Bernard Chazelle általi és legismertebb (determinisztikus) minimum feszítő fa algoritmus részben szintén a Borůvka-algoritmuson alapszik, és O(E α(E,V)) futási idővel bír, ahol α az Ackermann-függvény inverze.[10] Ezek a randomizált és determinisztikus algoritmusok egyesítik a Borůvka-algoritmusának lépéseit, csökkentve a csatlakozva maradt komponensek számát, más típusú lépésekkel, amelyek csökkentik az élek számát a komponenspárok között.

Jegyzetek[szerkesztés]

  1. ↑ Borůvka (1926). „O jistém problému minimálním” (czech, german nyelven). Práce Mor. Přírodověd. Spol. V Brně III 3, 37–58. o.  
  2. ↑ Borůvka (1926). „Příspěvek k řešení otázky ekonomické stavby elektrovodních sítí (Contribution to the solution of a problem of economical construction of electrical networks)” (czech nyelven). Elektronický Obzor 15, 153–154. o.  
  3. ↑ Nešetřil (2001). „Otakar Borůvka on minimum spanning tree problem: translation of both the 1926 papers, comments, history”. Discrete Mathematics 233 (1–3), 3–36. o. DOI:10.1016/S0012-365X(00)00224-7.  
  4. ↑ Choquet (1938). „Étude de certains réseaux de routes” (french nyelven). Comptes Rendus de l'Académie des Sciences 206, 310–313. o.  
  5. ↑ Florek (1951). „Sur la liaison et la division des points d'un ensemble fini” (french nyelven). Colloquium Mathematicae 2, 282–285. o.  
  6. ↑ Sollin (1965). „Le tracé de canalisation” (french nyelven). Programming, Games, and Transportation Networks.  
  7. ↑ Eppstein, David.szerk.: Sack: Spanning trees and spanners, Handbook of Computational Geometry. Elsevier, 425–461. o. (1999) 
  8. ↑ Bader (2006. április 8.). „Fast shared-memory algorithms for computing the minimum spanning forest of sparse graphs”. Journal of Parallel and Distributed Computing 66 (11), 1366–1378. o. DOI:10.1016/j.jpdc.2006.06.001.  
  9. ↑ Karger (1995. április 8.). „A randomized linear-time algorithm to find minimum spanning trees”. Journal of the ACM 42 (2), 321–328. o. DOI:10.1145/201019.201022.  
  10. ↑ Chazelle (2000). „A minimum spanning tree algorithm with inverse-Ackermann type complexity”. J. ACM 47 (6), 1028–1047. o. DOI:10.1145/355541.355562.  

Fordítás[szerkesztés]

Ez a szócikk részben vagy egészben a Borůvka's algorithm című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

A lap eredeti címe: „https://hu.wikipedia.org/w/index.php?title=Borůvka-algoritmus&oldid=25532329”