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

Вход: список рёбер графа с длинами. .

Выход: множество рёбер кратчайшего остова.

Упорядочить в порядке возрастания длин

{ номер рассматриваемого ребра }

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.

Дата добавления: 2014-11-20