Kruskalin algoritmi on tehokas algoritmi painotetun yhdistetyn suuntaamattoman graafin minimivirittävän puun rakentamiseen . Algoritmia käytetään myös likiarvojen löytämiseen Steiner-ongelmalle [1] .
Algoritmin kuvasi Joseph Kraskal vuonna 1956 , tämä algoritmi on melkein sama kuin Boruvkan algoritmi , jonka Otakar Boruvka ehdotti vuonna 1926.
Aluksi nykyinen reunajoukko asetetaan tyhjäksi. Sitten, kun se on mahdollista, suoritetaan seuraava toimenpide: kaikista reunoista, joiden lisäys jo olemassa olevaan joukkoon ei aiheuta syklin esiintymistä siinä, valitaan vähimmäispainon reuna ja lisätään jo olemassa olevaan joukkoon . Kun tällaisia reunoja ei enää ole, algoritmi on valmis. Tietyn graafin aligraafi, joka sisältää kaikki sen kärjet ja löydetyn reunajoukon, on sen vähimmäispainoinen virittävä puu . Yksityiskohtainen kuvaus algoritmista löytyy kirjallisuudesta [2] .
Ennen kuin algoritmi käynnistyy, on tarpeen lajitella reunat painon mukaan, mikä vie O(E × log(E)) aikaa. Sen jälkeen on kätevää tallentaa liitetyt komponentit hajautettujen joukkojen järjestelmänä . Tässä tapauksessa kaikki operaatiot edellyttävät O(E × α(E, V)) , jossa α on Ackermannin funktion käänteisfunktio . Koska millä tahansa käytännön ongelmalla α(E, V) < 5 , niin se voidaan ottaa vakiona, joten Kruskalin algoritmin kokonaisajoaika voidaan ottaa O(E * log(E)) .
Kruskalin algoritmi todellakin löytää minimipainon virittävän puun, koska se on Rado-Edmonds-algoritmin [3] erikoistapaus graafiselle matroidille , jossa riippumattomat joukot ovat asyklisiä reunajoukkoja.
| Kuva | Kuvaus |
|---|---|
| Reunojen AD ja CE vähimmäispaino on 5. Reuna AD valitaan mielivaltaisesti (korostettu kuvassa). Tuloksena saadaan joukko valittuja pisteitä ( A , D ). | |
| Nyt reunalla CE on pienin paino, joka on 5 . Koska CE :n lisääminen ei muodosta sykliä, valitsemme sen toiseksi reunaksi. Koska tällä reunalla ei ole yhteisiä pisteitä olemassa olevan valittujen pisteiden ( A , D ) kanssa, saadaan toinen joukko valittuja pisteitä ( C , E ). | |
| Vastaavasti valitaan reuna DF , jonka paino on 6. Tässä tapauksessa sykliä ei tapahdu, koska ei ole olemassa (valitsemattomien joukossa) reunoja, joilla on molemmat kärjet yhdestä ( A , D , F ) tai toisesta ( C , E ) joukko valittuja pisteitä. | |
| Seuraavat reunat ovat AB ja BE painolla 7. Kuvassa korostettu reuna AB valitaan sattumanvaraisesti. Tämä lisää kärkipisteen B ensimmäiseen valittujen pisteiden joukkoon ( A , B , D , F ). Aiemmin valitsematon reuna BD on korostettu punaisella, koska sen kärjet sisältyvät valittujen pisteiden joukkoon ( A , B , D , F ), ja siksi B :n ja D :n välillä on jo polku (vihreä) (jos tämä reuna on valittu, ja kierrä sitten ABD ).
Seuraava reuna voidaan valita vasta, kun kaikki syklit on löydetty. | |
| Vastaavasti valitaan reuna BE painolla 7. Koska tällä reunalla on pisteet molemmissa valittujen kärkijoukoissa ( A , B , D , F ) ja ( C , E ), nämä joukot yhdistetään yhdeksi ( A , B ) , C , D , E , F ). Tässä vaiheessa monet muut reunat on korostettu punaisella, koska valittujen kärkien joukot ja siten valittujen reunojen joukot ovat yhdistyneet. Nyt BC luo BCE- syklin , DE luo DEBA - syklin ja FE luo FEBAD- syklin . | |
| Algoritmi päättyy siihen, että lisätään reuna EG , jonka paino on 9. Valittujen pisteiden lukumäärä ( A , B , C , D , E , F , G ) = 7 vastaa graafin kärkien määrää. Pienin virittävä puu on rakennettu. |
| Kaavion hakualgoritmit | ||
|---|---|---|
| Tietämättömät menetelmät | ||
| Tietoon perustuvat menetelmät | ||
| Pikanäppäimet | ||
| Vähintään ulottuva puu | ||
| muu | ||