Алгоритм Краскала

1. Упорядочиваем ребра графа в порядке неубывания их весов.

2. Строим пустой граф , где - количество вершин исходного графа

3. На каждом шаге к уже сформированному текущему графу, добавляется ребро из списка ребер исходного графа с минимальным весом. Добавляемое ребро не должно приводить к образованию цикла.

4. Алгоритм заканчивает работу, если количество ребер в формируемом графе станет равным .

Пример: алгоритм Краскала

Список ребер

e₁=(1, 2), (4, 3) - 1

e₂=(1, 5) - 2

e₃=(4, 5) - 3

e₄=(1, 3), (2, 3) - 4

e₅=(2, 4) - 5

Остов кратчайших маршрутов:

M=((1, 2), (4,3),(1, 5), (4,5))

Общий суммарный вес = 7.