Borůvka-algoritmus

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

A Boruvka-algoritmus animációja

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

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

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

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

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.