2015-06-24
495
Задача о поиске остовного дерева наименьшего веса: дан взвешенный граф W=(G, j), G = (V,Е). Требуется найти остов G(V, T) такой, что сумма весов его рёбер была наименьшей. Схема алгоритма: остов строится из несвязных компонент, соединяемых между собой рёбрами минимального веса (длины). Начальное множество состоит из множества вершин, граф задан списком рёбер Е. На каждом шаге ищется свободное ребро минимального веса, соединяющее между собой несвязные компоненты будущего остова. Если минимальное ребро приводит к циклу, то оно отбрасывается. Выход – минимальный остов.
Конкретной реализацией этой схемы является алгоритм Краскала.
Вход: список Е рёбер графа G с длинами.
Выход: множество Т рёбер кратчайшего остова.
1. Т › Æ.
2. Упорядочить Е в порядке возрастания длин – формируется очередь.
3. Цикл по k=1,n–1:
Проверка: T Çe(k) даёт цикл или нет.
Если цикл, то k › k+1, возврат
Если нет цикла, то Т › T Çe(k), k › k+1, возврат
