bélyegkép|228x228px| 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. Az algoritmust Choquet fedezte fel újra 1938-ban; majd Florek, Łukasiewicz, Perkal, Steinhaus és Zubrzycki 1951-ben; és újra Georges Sollin 1965-ben. 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.
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.
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ő várható futási idővel. A Bernard Chazelle általi és legismertebb (determinisztikus) minimum feszítő fa algoritmus részben szintén a Borůvka-algoritmuson alapszik, és futási idővel bír, ahol α az Ackermann-függvény inverze. 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
Fordítás
Kategória:Feszítőfa Kategória:Gráfalgoritmusok Kategória:Keresőalgoritmusok