Kruskals algoritm är en effektiv algoritm för att konstruera det minsta spännträdet för en viktad sammankopplad oriktad graf . Algoritmen används också för att hitta några approximationer för Steinerproblemet [1] .
Algoritmen beskrevs av Joseph Kraskal 1956 , denna algoritm är nästan densamma som Boruvkas algoritm som föreslogs av Otakar Boruvka 1926.
Inledningsvis är den aktuella uppsättningen kanter inställd på tom. Sedan, medan det är möjligt, utförs följande operation: från alla kanter vars tillägg till den redan befintliga uppsättningen inte kommer att orsaka utseendet på en cykel i den, väljs kanten med minsta vikt och läggs till den redan befintliga uppsättningen . När det inte finns fler sådana kanter är algoritmen klar. En subgraf av en given graf som innehåller alla dess hörn och den hittade uppsättningen kanter är dess minsta viktspännande träd . En detaljerad beskrivning av algoritmen finns i litteraturen [2] .
Innan algoritmen startar är det nödvändigt att sortera kanterna efter vikt, vilket tar O(E × log(E)) tid. Efter det är det bekvämt att lagra de anslutna komponenterna som ett system med disjunkta uppsättningar . Alla operationer i detta fall kommer att ta O(E × α(E, V)) , där α är funktionen invers till Ackermann-funktionen . Eftersom för alla praktiska problem α(E, V) < 5 , så kan vi ta det som en konstant, så den totala körtiden för Kruskals algoritm kan tas som O(E * log(E)) .
Kruskals algoritm hittar verkligen ett minimumviktspännande träd, eftersom det är ett specialfall av Rado-Edmonds-algoritmen [3] för den grafiska matroiden , där de oberoende uppsättningarna är acykliska uppsättningar av kanter.
| Bild | Beskrivning |
|---|---|
| Kanter AD och CE har en minimivikt på 5. En kant AD väljs godtyckligt (markerad i figuren). Som ett resultat får vi en uppsättning utvalda hörn ( A , D ). | |
| Nu har kanten CE den minsta vikten lika med 5 . Eftersom att lägga till CE inte bildar en cykel väljer vi det som andra kant. Eftersom denna kant inte har några gemensamma hörn med den befintliga uppsättningen av valda hörn ( A , D ), får vi den andra uppsättningen av valda hörn ( C , E ). | |
| På liknande sätt väljer vi kanten DF , vars vikt är lika med 6. I det här fallet inträffar ingen cykel, eftersom det inte finns (bland de ovalda) kanterna som har båda hörnen från den ena ( A , D , F ) eller den andra ( C , E ) uppsättning av valda hörn. | |
| Nästa kanter är AB och BE med vikt 7. Den kant AB som är markerad i figuren väljs slumpmässigt. Detta lägger till vertex B till den första uppsättningen av valda hörn ( A , B , D , F ). Den tidigare omarkerade kanten BD är markerad i rött, eftersom dess hörn ingår i uppsättningen av valda hörn ( A , B , D , F ), och därför finns det redan en väg (grön) mellan B och D (om detta kant valdes, cykla sedan ABD ).
Nästa kant kan endast väljas efter att alla cykler har hittats. | |
| På liknande sätt väljs en kant BE med vikten 7. Eftersom denna kant har hörn i båda uppsättningarna av valda hörn ( A , B , D , F ) och ( C , E ), slås dessa uppsättningar samman till en ( A , B ) C , D , E , F ) . I detta skede är många fler kanter markerade i rött, eftersom uppsättningarna av valda hörn, och därför uppsättningarna av valda kanter, har slagits samman. Nu kommer BC att skapa en BCE - cykel , DE kommer att skapa en DEBA - cykel och FE kommer att skapa en FEBAD - cykel . | |
| Algoritmen avslutas med tillägg av en kant EG med vikt 9. Antalet valda hörn ( A , B , C , D , E , F , G ) = 7 motsvarar antalet hörn i grafen. Det minsta spännträdet har konstruerats. |
| Algoritmer för grafsökning | ||
|---|---|---|
| Oinformerade metoder | ||
| Informerade metoder | ||
| Genvägar | ||
| Minsta spännträd | ||
| Övrig | ||