A Kruskal-algoritmus egy hatékony algoritmus egy súlyozott összekapcsolt irányítatlan gráf minimális feszítőfájának megalkotására . Emellett az algoritmust arra is használják, hogy találjanak néhány közelítést a Steiner-probléma számára [1] .
Az algoritmust Joseph Kraskal írta le 1956 -ban , ez az algoritmus majdnem megegyezik Boruvka algoritmusával , amelyet Otakar Boruvka javasolt 1926-ban.
Kezdetben az aktuális élkészlet üresre van állítva. Ezután, amíg lehetséges, a következő műveletet hajtjuk végre: mindazon élekről, amelyeknek a már meglévő halmazhoz való hozzáadása nem okoz benne ciklus megjelenését, kiválasztjuk a minimális súlyú élt, és hozzáadjuk a már meglévő halmazhoz. . Ha már nincs ilyen él, az algoritmus befejeződik. Egy adott gráfnak az összes csúcsát és a talált élhalmazt tartalmazó részgráfja a minimális súlyú feszítőfa . Az algoritmus részletes leírása megtalálható a szakirodalomban [2] .
Mielőtt az algoritmus elindulna, az éleket súly szerint rendezni kell, ami O(E × log(E)) időt vesz igénybe. Ezt követően célszerű a csatlakoztatott alkatrészeket diszjunkt készletek rendszereként tárolni . Ebben az esetben minden művelet O(E × α(E, V)) lesz, ahol α az Ackermann-függvény inverze . Mivel bármilyen gyakorlati feladatra α(E, V) < 5 , akkor ezt konstansnak vehetjük, így a Kruskal-algoritmus teljes futási idejét O(E * log(E)) -nek vehetjük .
Kruskal algoritmusa valóban talál egy minimális súlyú feszítőfát, mivel ez a Rado-Edmonds algoritmus [3] speciális esete a grafikus matroid számára , ahol a független halmazok aciklikus élhalmazok.
| Kép | Leírás |
|---|---|
| Az AD és CE élek minimális súlya 5. Az AD él önkényesen van kiválasztva (az ábrán kiemelve). Ennek eredményeként kiválasztott csúcsok halmazát kapjuk ( A , D ). | |
| Most a CE élnek van a legkisebb súlya 5 . Mivel a CE hozzáadása nem képez ciklust, ezt választjuk második élnek. Mivel ennek az élnek nincs közös csúcsa a kiválasztott csúcsok meglévő halmazával ( A , D ), a kiválasztott csúcsok második halmazát ( C , E ) kapjuk. | |
| Hasonlóképpen kiválasztjuk a DF élt , amelynek súlya 6. Ebben az esetben nem fordul elő ciklus, mivel nem létezik (a ki nem választott élek között) olyan él, amelynek mindkét csúcsa az egyikből ( A , D , F ) vagy a másodikból származik. ( C , E ) kiválasztott csúcsok halmaza. | |
| A következő élek AB és BE 7 súllyal. Az ábrán kiemelt AB élt véletlenszerűen választjuk ki. Ez hozzáadja a B csúcsot a kiválasztott csúcsok első halmazához ( A , B , D , F ). A korábban ki nem választott BD él piros színnel van kiemelve, mivel annak csúcsai benne vannak a kiválasztott csúcsok halmazában ( A , B , D , F ), és ezért már van egy út (zöld) B és D között (ha ez éle lett kiválasztva, majd ciklus ABD ).
A következő él csak az összes ciklus megtalálása után választható ki. | |
| Hasonlóképpen egy BE élt 7-es súllyal választunk ki. Mivel ennek az élnek a kiválasztott csúcsok mindkét halmazában ( A , B , D , F ) és ( C , E ) vannak csúcsok, ezek a halmazok összevonódnak egy ( A , B ) , C , D , E , F ). Ebben a szakaszban sokkal több él van kiemelve pirossal, mivel a kiválasztott csúcsok halmazai, és így a kiválasztott élek halmazai összeolvadtak. Most a BC létrehoz egy BCE ciklust , a DE egy DEBA ciklust , és az FE létrehoz egy FEBAD ciklust . | |
| Az algoritmus egy EG él hozzáadásával ér véget, amelynek súlya 9. A kiválasztott csúcsok száma ( A , B , C , D , E , F , G ) = 7 megfelel a gráf csúcsainak számának. A minimális feszítőfa megépült. |
| Grafikon keresési algoritmusok | ||
|---|---|---|
| Tájékozatlan módszerek | ||
| Tájékozott módszerek | ||
| Parancsikonok | ||
| Minimálisan átívelő fa | ||
| Egyéb | ||