Minimala uppspännande träd

År 1926 fick Otakar Borůvka i uppdrag att planera elnätet i södra Mähren så billigt som möjligt. Hans fråga, hur man förbinder varje ort med minsta totala längd ledning, är problemet med minimalt uppspännande träd, och det har några av de enklaste och mest eleganta svaren i hela datavetenskapen.

En graf vars kanter har längder, med de korta kanterna i ett växande träd markerade, en överhoppad kant som skulle sluta en cykel streckad i rött, och listan över kanter som återstår att prova nedanför
En graf vars kanter har längder, med de korta kanterna i ett växande träd markerade, en överhoppad kant som skulle sluta en cykel streckad i rött, och listan över kanter som återstår att prova nedanför

Problemet

Ta en sammanhängande graf vars kanter har längder, eller kostnader. Ett uppspännande träd är en mängd kanter som förbinder alla noder och inte innehåller någon cykel; med n noder har det alltid exakt n − 1 kanter, eftersom varje kant förbinder en nod till. Bland alla uppspännande träd har ett minimalt uppspännande träd minst total längd. En graf kan ha ett enormt antal uppspännande träd, men man behöver inte prova alla.

Varför girighet fungerar

Dela noderna i två grupper på valfritt sätt. Den kortaste kanten mellan grupperna hör alltid till något minimalt uppspännande träd: om ett träd i stället använde en längre kant mellan grupperna skulle ett byte till den kortare förbinda samma noder billigare. Det här är snittegenskapen. Den andra sidan av myntet är cykelegenskapen: den längsta kanten i en cykel behövs aldrig. Båda algoritmerna nedan tillämpar bara dessa regler om och om igen.

Ett exempel

Ta kanterna A–B med längd 1, B–C 2, A–C 3, C–D 4 och B–D 5. Kruskals algoritm tar A–B, sedan B–C, hoppar sedan över A–C, eftersom A och C redan är förbundna och den skulle sluta en cykel, och tar sedan C–D. Trädet har tre kanter för fyra noder, så det är klart, med total längd 7, och B–D tittas aldrig ens på. Prims algoritm från A lägger först till B via A–B; B:s kant B–C (2) slår A–C (3) som väg till C, så C ansluter via B–C; C:s kant C–D (4) slår B–D (5), så D ansluter via C–D. Samma träd, samma 7.

Kruskal, Prim och Borůvka

Kruskals algoritm, publicerad av Joseph Kruskal 1956, sorterar kanterna och använder en union-find-struktur för att hoppa över kanter inom en del, så arbetet växer med E log E. Prims algoritm beskrevs först av Vojtěch Jarník 1930 och återupptäcktes av Robert Prim 1957 och Edsger Dijkstra 1959; med en binär heap växer arbetet med E log V, och med en enkel array med V², vilket är bra för täta grafer. Borůvkas algoritm från 1926 låter varje del ta sin kortaste utgående kant samtidigt, vilket passar parallella datorer.

Otakar Borůvka 1981. År 1926 ombads han planera elnätet i södra Mähren så billigt som möjligt och gav den första algoritmen för ett minimalt uppspännande träd.
Otakar Borůvka 1981. År 1926 ombads han planera elnätet i södra Mähren så billigt som möjligt och gav den första algoritmen för ett minimalt uppspännande träd.

Användning

Minimala uppspännande träd används för att planera billiga nät av kablar, rör och vägar. De delar in data i kluster: ta bort trädets längsta kanter, så är delarna som blir kvar klustren. De ger en snabb rundtur för handelsresandeproblemet som är högst dubbelt så lång som den bästa när avstånden följer triangelolikheten. Och Kruskals eller Prims algoritm på ett rutnät med slumpmässiga kantlängder är ett klassiskt sätt att skapa en labyrint.

Utforska

Öppna appen, välj Kruskal eller Prim och tryck på Steg. Med Kruskal listas kanterna som återstår att prova under grafen, från kortast till längst; kanter som skulle sluta en cykel ritas streckade i rött. Med Prim listas noderna som väntar på att ansluta, med längden på sin bästa kant, som ritas streckad. Kör båda på samma graf och jämför: ordningen skiljer sig, men den totala längden är alltid densamma.

Ofta ställda frågor

Hur många kanter har ett uppspännande träd?

Exakt en färre än antalet noder. Färre kanter skulle inte kunna förbinda alla noder, och en till skulle alltid skapa en cykel.

Vilken är snabbast, Kruskal eller Prim?

Kruskals algoritm, som sorterar kanterna, är oftast enklare och snabb på glesa grafer med få kanter. Prims algoritm med en heap klarar sig bra på täta grafer, och med en vanlig array behöver den ungefär V² steg, oavsett hur många kanter det finns.

Vad är union-find?

En datastruktur som håller reda på vilka noder som finns i samma del. Den svarar på ”är de här två förbundna?” och slår ihop två delar nästan direkt, vilket är precis vad Kruskals algoritm behöver för varje kant.

Fungerar ett minimalt uppspännande träd för riktade grafer?

Inte som det är. För grafer med enkelriktade kanter är motsvarande problem den minimala uppspännande arborescensen, som löses av Chu–Liu/Edmonds algoritm.

Redo att prova det?

Öppna PictorX i din webbläsare - ingen installation, inget kreditkort krävs för att starta.

Bygg ett minimalt uppspännande träd