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ő.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2e/Boruvka%27s_algorithm_%28Sollin%27s_algorithm%29_Anim.gif/228px-Boruvka%27s_algorithm_%28Sollin%27s_algorithm%29_Anim.gif)
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ésAz 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ésA 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ésEgyéb algoritmusok
szerkesztésA 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- ↑ 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.
- ↑ 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.
- ↑ 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.
- ↑ Choquet (1938). „Étude de certains réseaux de routes” (french nyelven). Comptes Rendus de l'Académie des Sciences 206, 310–313. o.
- ↑ Florek (1951). „Sur la liaison et la division des points d'un ensemble fini” (french nyelven). Colloquium Mathematicae 2, 282–285. o.
- ↑ Sollin (1965). „Le tracé de canalisation” (french nyelven). Programming, Games, and Transportation Networks.
- ↑ Eppstein, David.szerk.: Sack: Spanning trees and spanners, Handbook of Computational Geometry. Elsevier, 425–461. o. (1999)
- ↑ Bader (2006. július 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.
- ↑ Karger (1995. július 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.
- ↑ 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ésEz 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.