Algorytm Kruskala – algorytm grafowy wyznaczający minimalne drzewo rozpinające dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład algorytmu zachłannego.
Został on po raz pierwszy opublikowany przez Josepha Kruskala w 1956 roku w czasopiśmie Proceedings of the American Mathematical Society.
Algorytm Utwórz las L z wierzchołków oryginalnego grafu – każdy wierzchołek jest na początku osobnym drzewem. Utwórz zbiór S zawierający wszystkie krawędzie oryginalnego grafu. Dopóki S nie jest pusty oraz L nie jest jeszcze drzewem rozpinającym: Wybierz i usuń z S jedną z krawędzi o minimalnej wadze. Jeśli krawędź ta łączyła dwa różne drzewa, to dodaj ją do lasu L, tak aby połączyła dwa odpowiadające drzewa w jedno. W przeciwnym wypadku odrzuć ją.
Po zakończeniu algorytmu L jest minimalnym drzewem rozpinającym.
Implementacja i złożoność Jako zbiór E można wziąć tablicę wszystkich krawędzi posortowaną według wag. Wtedy w każdym kroku najmniejsza krawędź to po prostu następna w kolejności.