Алгоритм Краскала
Вход: список 
рёбер графа 
с длинами. 
.
Выход: множество 
рёбер кратчайшего остова.
Упорядочить в порядке возрастания длин
{ номер рассматриваемого ребра }
for 
from 1 to 
do
while добавление ребра 
образует цикл в do
{пропустить ребро }
end while
{добавить это ребро в SST }
end for
(SST-Shortest Sceleton Tree - стандартное обозначение для кратчайшего остова).
Пример. Дан нагруженный граф . Необходимо построить минимальное остовное дерево 
.
Алгоритм: Строим таблицу, в которую заносим все ребра с их стоимостями в порядке возрастания. На каждом шаге алгоритма включаем в остовное дерево ребро графа минимальной стоимости, проверяя, не образуется ли цикл с уже включенными в дерево ребрами.
Рисунок 6.72
| Шаг | Ребро | Стоимость | +/- |
| (1, 7) | включаем | ||
| (3, 4) | включаем | ||
| (2, 7) | включаем | ||
| (3, 7) | включаем | ||
| (2, 3) | образует цикл, не включаем | ||
| (4, 7) | образует цикл, не включаем | ||
| (1, 5) | включаем | ||
| (1, 2) | образует цикл, не включаем | ||
| (1, 6) | Включаем. Все вершины включены в остов. Конец. | ||
| (5, 7) | |||
| (5, 6) | |||
| (6, 7) |
Рисунок 6.73
Рисунок 6.74
Рисунок 6.75
В результате работы алгоритма получаем остов минимальной стоимости: 
=57.