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:

Kezdetben legyen egy üres élhalmaz (egy átívelő erdőt képvisel, amelyben minden csúcs külön faként szerepel). $T$
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): $T$ $T$ $V-1$ $V$
- 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). $T$
- Adja hozzá az összes talált élt a készlethez . $T$
Az így kapott élhalmaz a bemeneti gráf minimális feszítőfája. $T$

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). $O(\log V)$ $O(E)$ $O(E\log V)$ $V$ $E$

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. $O(E)$

Lásd még

Irodalom

Sedgwick R. Alapvető algoritmusok C++ nyelven, 5. rész. Algoritmusok gráfokon. ISBN 5-93772-082-2 .

Jegyzetek

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

Grafikon keresési algoritmusok
Tájékozatlan módszerek	Kétirányú keresés Sugárkeresés Lexikográfiai szélesség első keresés Szélesség első keresés Keresés költségkritérium szerint Mélységi első keresés Keresés visszafelé Keresés a csúcsra való mászás alapján Mélységben korlátozott keresés Mélység-első keresés iteratív elmélyítéssel
Tájékozott módszerek	Alfa béta vágás Elágazás és kötött módszer Keresés az első legjobb találat alapján A* B* D* Átmeneti pont keresése IDA* Rekurzív keresés az első legjobb találaton SMA*
Parancsikonok	Hullám algoritmus Bellman-Ford algoritmus Dijkstra algoritmusa Johnson algoritmus Levit algoritmusa Floyd-Warshall algoritmus Edge keresés
Minimálisan átívelő fa	Boruvka algoritmusa Prim algoritmusa Kruskal algoritmusa
Egyéb	British Museum algoritmus Edmonds algoritmus Fa bejárás Legközelebbi szomszéd algoritmus az utazó eladó problémájában