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 .
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:
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.
Grafikon keresési algoritmusok | ||
---|---|---|
Tájékozatlan módszerek | ||
Tájékozott módszerek | ||
Parancsikonok | ||
Minimálisan átívelő fa | ||
Egyéb |