Отсортировать ребра в порядке возрастания весов инициализировать структуру разбиений.
edgeCount=l.
while edgeCount<=E and includedCount<=М-l do.
parentl=FindRoot (edge[edgeCount]. start).
parent2=FindRoot (edge[edgeCount]. end).
if parentl/=parent2 then.
добавить edge[edgeCount] в остовное дерево.
includedCount=includedCount=l.
Union (parent1,parent2).
end if.
edgeCount=edgeCount+l.
end while.
E — число ребер в графе;
V — число вершин в графе.
edgeCount — переменная;
includedCount — переменная;
Parent — массив, в котором под каждый элемент множества, с которым мы собираемся работать, отведена одна ячейка;
FindRoot (x) — (x элемент, для которого мы хотим найти корень части, его содержащей) процедура, начинающая с ячейки Parent [x], в которой хранится номер непосредственного предка элемента x;
Union — функция, выполняющая объединение двух частей в одну.
Блок-схема алгоритма
На рисунке 1 представлена общая схема алгоритма.
Рисунок 1 Общая схема На рисунке 2 представлена блок-схема алгоритма сортировки вставками.
Рисунок 2 Блок-схема алгоритма сортировки вставками На рисунке 3 представлена блоксхема алгоритма Краскала.
Рисунок 3 Блоксхема алгоритма Краскала.
Сложность алгоритма
Сложность этого алгоритма совпадает со сложностью используемоего алгоритма сортировки, поскольку число операций в цикле while линейно по числу ребер. Поэтому сложность алгоритма Крускала поиска МОД равна O (Eog Е).
