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].