![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/5/5c/MST_kruskal_en.gif/640px-MST_kruskal_en.gif&w=640&q=50)
Algorytm Kruskala
Z Wikipedii, wolnej encyclopedia
Algorytm Kruskala – algorytm grafowy wyznaczający minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny[1]. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa[2]. Jest to przykład algorytmu zachłannego[2].
Szybkie fakty Rodzaj, Struktura danych ...
![]() Wizualizacja Algorytmu Kruskala | |
Rodzaj |
Wyznaczanie minimalnego drzewa rozpinającego |
---|---|
Struktura danych | |
Złożoność | |
Czasowa |
|
Zamknij
Został on po raz pierwszy opublikowany przez Josepha Kruskala w 1956 roku w czasopiśmie Proceedings of the American Mathematical Society[3].