Boruvka algoritmusa

Boruvka algoritmusa (vagy Boruvka-Sollin algoritmusa ) egy olyan algoritmus, amely a gráf minimális feszítőfáját keresi.

Először 1926-ban tette közzé Otakar Boruvka , mint módszert az optimális elektromos hálózat megtalálására Morvaországban . Többször újra felfedezték, például Florek , Perkal és Sollin . Ráadásul ez utóbbi volt az egyetlen nyugati tudós ezen a listán, ezért az algoritmust gyakran Sollin algoritmusaként emlegetik, különösen a párhuzamos számítástechnikai szakirodalomban .

Algoritmus

Az algoritmus működése több iterációból áll, amelyek mindegyike abból áll, hogy szekvenciálisan adunk hozzá éleket a gráf feszítőerdőjéhez , amíg az erdő fává nem válik , azaz egy összefüggő komponensből álló erdővé.

Az algoritmus a következőképpen írható le:

  1. Kezdetben legyen egy üres élhalmaz (egy átívelő erdőt képvisel, amelyben minden csúcs külön faként szerepel).
  2. Még nem fa (ami ekvivalens a feltétellel: míg az élek száma kisebb, mint , hol a csúcsok száma a gráfban):
    • Az élekkel ellátott részgráfban minden egyes összekapcsolt komponenshez (vagyis egy fához az átívelő erdőben) keresse meg a legolcsóbb élt, amely ezt a komponenst egy másik kapcsolódó összetevőhöz köti. (Feltételezzük, hogy az élek súlya eltérő, vagy valamilyen módon kiegészítve van elrendezve, így mindig lehetséges egyetlen élt találni a legkisebb súllyal).
    • Adja hozzá az összes talált élt a készlethez .
  3. Az így kapott élhalmaz a bemeneti gráf minimális feszítőfája.

Az algoritmus összetettsége

Minden iterációnál az átívelő erdőben lévő fák száma legalább a felére csökken, így az algoritmus összesen a legtöbb iterációt hajtja végre. Minden iteráció komplexitással megvalósítható , így az algoritmus teljes futási ideje az idő (itt és a gráf csúcsainak és éleinek száma).

Azonban bizonyos típusú gráfok, különösen a síkbeli gráfok esetében lecsökkenthető . [1] A Boruvka-féle algoritmuson alapuló randomizált minimális feszítőfa -algoritmus is létezik, amely átlagosan lineáris időben fut.

Lásd még

Irodalom

Jegyzetek

  1. Eppstein, David (1999), Spanning trees and spanners, Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry , Elsevier, p. 425–461  ; Mareš, Martin (2004), Két lineáris idő algoritmus az MST-hez kisebb zárt gráfosztályokon , Archivum mathematicum 40 (3): 315–320 , < http://www.emis.de/journals/AM/04-3 /am1139.pdf > Archiválva : 2009. május 9. a Wayback Machine -nél .