Szerkesztő:Franky515/Borůvka-algoritmus

A Borůvka-algoritmus egy mohó algoritmus 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őnek olyan gráf esetén amely nem kapcsolódik

Elsőként 1926-ban, Otakar Borůvka tette közzé, mint egy hatékony módszer Morvaország elektromos hálózatának kiépítéséhez. ^[1] ^[2] ^[3] Az algoritmust Choquet fedezte fel újra 1938-ban;^[4] és ismét Florek, Łukasiewicz, Perkal, Steinhaus és Zubrzycki által 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 azzal kezdődik, hogy megtaláljuk a grafikon minden csúcsához tartozó legkisebb súlyszélt, és hozzáadjuk ezeket az éleket az erdőhöz. Ezután megismétel egy hasonló eljárást, amikor megkeresi a legkisebb súlyú éleket mindegyik eddig épített fán egy másik fához, é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 kapcsolt 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 minimális feszítőerdőt képez.

Pszeudókód

Az egyes csúcsok vagy csatlakoztatott csúcsok halmaza egy "Összefüggő komponens" jelölése, pszeudókódja Bororvka algoritmusához:

 algoritmus Borůvka jelentése
  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 összefüggő komponenseit, és jelölje meg G minden egyes csúcsát az összefüggő 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:
        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 komponens, amelynek legalacsonyabb éle nem „Nincs” csinálni
      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) eltávolítani 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ásg, é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 közelében lévő 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 alkotóelem legkisebb súlyát hozzáadjuk. Egyes éleket kétszer 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 hozzáadjuk a fennmaradó két alkotóelem minimális súlyát. Ezek itt ugyanazok az élek. Az egyik elem megmarad és kész. A BD élet 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.

Megjegyzések

↑ 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. november 4.). „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. november 4.). „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.

[[Kategória:Feszítőfa]] [[Kategória:Gráfalgoritmusok]]

[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. november 4.). „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. november 4.). „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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]