Boruvkas algoritm

Boruvkas algoritm (eller Boruvka-Sollins algoritm ) är en algoritm för att hitta det minsta spännträdet i en graf.

Den publicerades första gången 1926 av Otakar Boruvka som en metod för att hitta det optimala elektriska nätverket i Mähren . Den har återupptäckts flera gånger, till exempel av Florek , Perkal och Sollin . Den sistnämnde var dessutom den enda västerländska vetenskapsmannen på denna lista, och därför kallas algoritmen ofta för Sollins algoritm, särskilt i parallellberäkningslitteraturen .

Algoritm

Funktionen av algoritmen består av flera iterationer, som var och en består i att sekventiellt lägga till kanter till grafens spännande skog , tills skogen förvandlas till ett träd , det vill säga en skog som består av en ansluten komponent.

Algoritmen kan beskrivas på följande sätt:

Låt först vara en tom uppsättning kanter (representerar en spännande skog där varje vertex ingår som ett separat träd). $T$
Är ännu inte ett träd (vilket motsvarar villkoret: medan antalet kanter i är mindre än , där är antalet hörn i grafen): $T$ $T$ $V-1$ $V$
- För varje ansluten komponent (det vill säga ett träd i den spännande skogen) i subgrafen med kanter , hitta den billigaste kanten som ansluter denna komponent till någon annan ansluten komponent. (Det antas att vikterna på kanterna är olika, eller på något sätt extra beställda så att det alltid är möjligt att hitta en enda kant med minsta vikt). $T$
- Lägg till alla hittade kanter till setet . $T$
Den resulterande uppsättningen kanter är det minsta spännträdet i inmatningsgrafen. $T$

Algoritmens komplexitet

Vid varje iteration halveras antalet träd i den spännande skogen minst, så algoritmen utför som mest iterationer totalt. Varje iteration kan implementeras med komplexitet , så den totala körtiden för algoritmen är tid (här och är antalet hörn och kanter i grafen, respektive). $O(\log V)$ $O(E)$ $O(E\log V)$ $V$ $E$

För vissa typer av grafer, särskilt plana , kan den dock reduceras till . [1] Det finns också en randomiserad minimum spaning tree -algoritm baserad på Boruvkas algoritm som körs i genomsnitt i linjär tid. $O(E)$

Se även

Litteratur

Sedgwick R. Grundläggande algoritmer i C++, del 5. Algoritmer på grafer. ISBN 5-93772-082-2 .

Anteckningar

↑ Eppstein, David (1999), Spanning trees and spanners, i Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry , Elsevier, sid. 425–461 ; Mareš, Martin (2004), Two linear time algorithms for MST on minor closed graph classes , Archivum mathematicum vol. 40 (3): 315–320 , < http://www.emis.de/journals/AM/04-3 /am1139.pdf > Arkiverad 9 maj 2009 på Wayback Machine .

Algoritmer för grafsökning
Oinformerade metoder	Dubbelriktad sökning Strålsökning Lexikografisk bredd första sökning Utöka första sökningen Sök efter kostnadskriterium Djup första sökning Backtracking sökning Sök genom att klättra till toppen Djupbegränsad sökning Djup-första sökning med iterativ fördjupning
Informerade metoder	Alfa beta-klippning Gren och bunden metod Sök efter första bästa matchning A* B* D* Att hitta en övergångspunkt IDA* Rekursiv sökning på den första bästa matchningen SMA*
Genvägar	Vågalgoritm Bellman-Ford algoritm Dijkstras algoritm Johnsons algoritm Levits algoritm Floyd-Warshall algoritm Kantsökning
Minsta spännträd	Boruvkas algoritm Prims algoritm Kruskals algoritm
Övrig	British Museum Algoritm Edmonds algoritm Trädpassering Algoritmen för närmaste granne i problemet med resande säljare