Kruskals algoritme er en effektiv algoritme til at konstruere minimumspændingstræet for en vægtet forbundet urettet graf . Algoritmen bruges også til at finde nogle tilnærmelser til Steiner-problemet [1] .
Algoritmen blev beskrevet af Joseph Kraskal i 1956 , denne algoritme er næsten den samme som Boruvkas algoritme foreslået af Otakar Boruvka i 1926.
Til at begynde med er det aktuelle sæt kanter sat til tomt. Så, mens det er muligt, udføres følgende handling: fra alle kanter, hvis tilføjelse til det allerede eksisterende sæt ikke vil forårsage udseendet af en cyklus i det, vælges kanten med minimumvægt og tilføjes til det allerede eksisterende sæt . Når der ikke er flere sådanne kanter, er algoritmen færdig. En undergraf af en given graf, der indeholder alle dens spidser og det fundne sæt af kanter, er dets minimumvægtspændende træ . En detaljeret beskrivelse af algoritmen kan findes i litteraturen [2] .
Inden algoritmen starter, er det nødvendigt at sortere kanterne efter vægt, hvilket tager O(E × log(E)) tid. Derefter er det praktisk at opbevare de tilsluttede komponenter som et system af adskilte sæt . Alle operationer i dette tilfælde vil tage O(E × α(E, V)) , hvor α er funktionen invers til Ackermann-funktionen . Da for alle praktiske problemer α(E, V) < 5 , så kan vi tage det som en konstant, så den samlede køretid for Kruskals algoritme kan tages som O(E * log(E)) .
Kruskals algoritme finder faktisk et minimum vægtspændende træ, da det er et specialtilfælde af Rado-Edmonds algoritmen [3] for den grafiske matroide , hvor de uafhængige sæt er acykliske sæt af kanter.
| Billede | Beskrivelse |
|---|---|
| Kanter AD og CE har en minimumsvægt på 5. En kant AD vælges vilkårligt (fremhævet i figuren). Som et resultat får vi et sæt udvalgte hjørner ( A , D ). | |
| Nu har kanten CE den mindste vægt lig med 5 . Da tilføjelse af CE ikke danner en cyklus, vælger vi det som den anden kant. Da denne kant ikke har nogen fælles toppunkter med det eksisterende sæt af udvalgte toppunkter ( A , D ), får vi det andet sæt udvalgte toppunkter ( C , E ). | |
| På samme måde vælger vi kanten DF , hvis vægt er lig med 6. I dette tilfælde forekommer der ingen cyklus, da der ikke eksisterer (blandt de uvalgte) kanter, der har begge hjørner fra den ene ( A , D , F ) eller den anden ( C , E ) sæt af udvalgte hjørner. | |
| De næste kanter er AB og BE med vægt 7. Kanten AB fremhævet i figuren er valgt tilfældigt. Dette tilføjer toppunkt B til det første sæt af valgte toppunkter ( A , B , D , F ). Den tidligere ikke-valgte kant BD er fremhævet med rødt, da dens toppunkter er inkluderet i sættet af valgte toppunkter ( A , B , D , F ), og der derfor allerede er en sti (grøn) mellem B og D (hvis denne kant blev valgt, og cyklus derefter ABD ).
Den næste kant kan kun vælges efter at have fundet alle cyklusser. | |
| Tilsvarende vælges en kant BE med vægten 7. Da denne kant har toppunkter i begge sæt af udvalgte toppunkter ( A , B , D , F ) og ( C , E ), slås disse sæt sammen til én ( A , B ) C , D , E , F ) . På dette trin er mange flere kanter fremhævet med rødt, da sætene af udvalgte hjørner, og derfor sættene af valgte kanter, er slået sammen. Nu vil BC oprette en BCE -cyklus , DE vil oprette en DEBA -cyklus , og FE vil oprette en FEBAD- cyklus . | |
| Algoritmen afsluttes med tilføjelse af en kant EG med vægt 9. Antallet af udvalgte toppunkter ( A , B , C , D , E , F , G ) = 7 svarer til antallet af toppunkter i grafen. Minimumspændingstræet er blevet konstrueret. |
| Algoritmer til grafsøgning | ||
|---|---|---|
| Uoplyste metoder | ||
| Informerede metoder | ||
| Genveje | ||
| Minimumspændende træ | ||
| Andet | ||