Boruvkas algoritme

Boruvkas algoritme (eller Boruvka-Sollins algoritme ) er en algoritme til at finde det mindste spændingstræ i en graf.

Den blev først udgivet i 1926 af Otakar Boruvka som en metode til at finde det optimale elektriske netværk i Mähren . Den er blevet genopdaget flere gange, for eksempel af Florek , Perkal og Sollin . Sidstnævnte var desuden den eneste vestlige videnskabsmand på denne liste, og derfor omtales algoritmen ofte som Sollins algoritme, især i parallel computing- litteraturen .

Algoritme

Funktionen af ​​algoritmen består af flere iterationer, som hver består i sekventielt at tilføje kanter til grafens spændende skov , indtil skoven bliver til et træ , det vil sige en skov bestående af én forbundet komponent.

Algoritmen kan beskrives som følger:

1. Lad først være et tomt sæt kanter (repræsenterer en spændende skov, hvor hvert hjørne er inkluderet som et separat træ).
2. Er endnu ikke et træ (hvilket svarer til betingelsen: mens antallet af kanter i er mindre end , hvor er antallet af hjørner i grafen):
   • For hver tilsluttet komponent (det vil sige et træ i den spændende skov) i undergrafen med kanter , skal du finde den billigste kant, der forbinder denne komponent med en anden tilsluttet komponent. (Det antages, at vægten af ​​kanterne er forskellige, eller på en eller anden måde ekstrabestilt, så det altid er muligt at finde en enkelt kant med minimumsvægt).
   • Tilføj alle fundne kanter til sættet .
3. Det resulterende sæt kanter er det mindste spændingstræ i inputgrafen.

Algoritmens kompleksitet

Ved hver iteration er antallet af træer i den spændende skov mindst halveret, så algoritmen udfører højst iterationer i alt. Hver iteration kan implementeres med kompleksitet , så den samlede køretid for algoritmen er tid (her og er henholdsvis antallet af hjørner og kanter i grafen).

For nogle typer grafer, især plane , kan den dog reduceres til . [1] Der er også en randomiseret minimum spændingstræ- algoritme baseret på Boruvkas algoritme, der kører i gennemsnit i lineær tid.

Se også

• Minimumspændende træ
• spændende træ
• Dijkstras algoritme
• Kruskals algoritme
• Omvendt sletningsalgoritme
• Prims algoritme

Litteratur

• Sedgwick R. Fundamentale algoritmer i C++, del 5. Algoritmer på grafer. ISBN 5-93772-082-2 .

Noter

1. ↑ Eppstein, David (1999), Spanning trees and spanners, i Sack, J.-R. & Urrutia, J., Handbook of Computational Geometry , Elsevier, s. 425-461  ; Mareš, Martin (2004), To lineære tidsalgoritmer for MST på mindre lukkede grafklasser , Archivum mathematicum bind 40 (3): 315–320 , < http://www.emis.de/journals/AM/04-3 /am1139.pdf > Arkiveret 9. maj 2009 på Wayback Machine .