Borůvkas algoritm är en girig algoritm för att hitta ett minsta uppspännande träd i en graf, eller en minsta uppspännande skog om grafen inte är sammanhängande.
Den publicerades först 1926 av Otakar Borůvka som en metod för att bygga ett effektivt elnät för Mähren. Algoritmen återupptäcktes av Choquet 1938, återigen av Florek, Łukasiewicz, Perkal, Steinhaus och Zubrzycki 1951, och återigen av Georges Sollin 1965. Denna algoritm kallas ofta Sollins algoritm, särskilt i litteratur om parallellberäkning .
Algoritmen börjar med att hitta för varje nod dess kant med minst vikt och lägga till denna kanta till skogen (ett eller flera träd som inte hänger samman). Sedan upprepar den en liknande steg där den hittar för varje träd kanten med den minsta vikten som går till ett annat träd och adderar alla dessa kanter till skogen. Varje upprepning av denna process minskar antalet träd till högst hälften av detta tidigare värde, så efter logaritmiskt många upprepningar avslutas processen. Då har man fått den minsta uppspännande skogen.
Komplexitet Man kan visa att Borůvkas algoritm tar iterationer av den yttre slingen tills den avslutas, och därför är dess tiden , där är antalet kanter och är antalet noder i (förutsatt att ). I plana grafer, och mer generellt i familjer av grafer som är slutna under nodsammanslagningsoperationer, kan den fås att gå i linjär tid genom att ta bort alla utom den kanten med lägst vikt mellan varje par av komponenter efter varje steg i algoritmen.
Exempel Bild komponenter Beskrivning200x200px {A} B {C} D {E} {F} {G} Detta är vår ursprungliga viktade graf. Siffrorna nära kanterna anger deras vikt. Inledningsvis är varje nod i sig en komponent (blå cirklar).200x200px {A, B, D, F} {C,E,G} I den första iterationen av den yttre slingan lägger man till kanten med lägst vikt från varje komponent. Vissa kanter väljs två gånger (AD, CE). Två komponenter återstår.200x200px {A, B, C, D, E, F, G} I den andra och sista iterationen adderas kanten med lägst vikt för var och en av de två återstående komponenterna. Dessa råkar vara samma kant. En komponent återstår och vi är klara. Kanten BD beaktas inte eftersom båda ändpunkterna är i samma komponent.
frameless|upright=1.35
Andra algoritmer Andra algoritmer för detta problem inkluderar Prims algoritm och Kruskals algoritm. Snabba parallella algoritmer kan erhållas genom att kombinera Prims algoritm med Borůvkas.
En snabbare randomiserad algoritm för minimalt uppspännande träd är delvis baserad på Borůvkas algoritm. Den utvecklades av Karger, Klein och Tarjan och dess tid går som . Den mest kända (deterministiska) algoritmen för ett minimalt uppspännande träd utvecklades av Bernard Chazelle. Den är också delvis baserad på Borůvkas och dess tid går som , där α är den inversa Ackermann-funktionen. Både dessa deterministiska och den randomiserade algoritmen kombinerar steg i Borůvkas algoritm genom att minska antalet komponenter som återstår att kopplas samman, med steg av en annan typ som minskar antalet kanter mellan par av komponenter.
Referenser
Noter
Kategori:Grafalgoritmer