Алгоритм Крускала предназначен для построения минимального остовного дерева взвешенного связного неориентированного графа. 1

Работа алгоритма начинается с вырожденного леса, где каждое дерево состоит из одной вершины. 3 Затем выполняется операция объединения двух деревьев (самыми короткими рёбрами). 3

Процесс происходит следующим образом: 5

1. Перед началом выполнения алгоритма все рёбра сортируются по весу (в порядке неубывания). 5
2. Перебираются все рёбра от первого до последнего (в порядке сортировки). 5
3. Если у текущего ребра его концы принадлежат разным поддеревьям, то эти поддеревья объединяются, а ребро добавляется к ответу. 5
4. По окончании перебора всех рёбер все вершины окажутся принадлежащими одному поддереву, и ответ найден. 5

Если обе вершины рассматриваемого ребра принадлежат одному и тому же связному компоненту, то такое ребро отбрасывается — в противном случае образуется цикл. 2

Алгоритм останавливается в двух случаях: 3

1. Если найдено определённое количество рёбер (например, V–1), то остовное дерево уже построено, и можно остановиться. 3
2. Если просмотрены все вершины, но не найдено V–1 древесных рёбер, то это означает, что граф не является связным. 3