УП_САОД_2003

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

Здесь построение MST начинается с графа, состоящего только из n вершин графа G и не имеющего ребер. Таким образом, каждая вершина является связанной (сама с собой) компонентой. Это дает n связных компонент. В процессе выполнения алгоритма связанные компоненты постепенно объединяются друг с другом, формируя остовное дерево.

При построении постепенно возрастающих связанных компонент поочередно проверяются ребра из множества E в порядке возрастания их длин. Если очередное ребро связывает две вершины из разных компонент, тогда оно добавляется в остовное дерево. Если это ребро связывает две вершины из одной компоненты, то оно отбрасывается, так как его добавление в связанную компоненту может привести к образованию цикла. Число ребер, необходимое для остовного дерева равно n-1. Граф связан, а значит E содержит как минимум такое их количество. Когда остовное дерево будет содержать n-1 ребер, алгоритм завершается.

Создать список ребер L, в неубывающем по длине порядке

while число отмеченных ребер < n-1 do begin

Удалить w из головы списка L;

if w соединяет две несвязных компоненты then

отметить w и добавить к MST

else {w - внутри компоненты}

не отмечать w {это приведет к циклу в MST}

end;

Рисунок 59. Алгоритм Крускала

Сложность алгоритма для графа с n вершинами и m ребрами пропорциональна O(m*log m).

Литература

^* Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. – М.: "Вильямс", 2001. – 384 с.
^* Бентли Д. Жемчужины творчества программистов. – М.: Радио и связь, 1990.
^* Вирт Н. Алгоритмы + структуры данных = программы. – М.: Мир, 1985.
^* Вирт Н. Алгоритмы и структуры данных. – М: Мир, 1989. – 360 с.
^* Грин Д., Кнут Д. Математические методы анализа алгоритмов. – М: Мир, 1987.
^* Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981.
^* Дейкстра Э. Дисциплина программирования. – М: Мир, 1978.
^* Кнут Д.Е. Искусство программирования для ЭВМ. В 3-х томах. – М.: Мир, 1976.
Кнут Д.Е. Искусство программирования. В 3-х томах. – М.: "Вильямс", 2000.
^* Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: Построение и анализ. – М.: МЦНМО, 2001.
Лэгсам Й., Огенстайн М. Структуры данных для персональных ЭВМ. – М.: Мир, 1989. – 586с.
^* Матьяш В.А., Путилов В.А., Фильчаков В.В., Щекин С.В. Структуры и алгоритмы обработки данных. – Апатиты, КФ ПетрГУ, 2000. – 80 с.
^* Оре О. Графы и их применение. – М.: Мир, 1965.
^* Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. Теория и практика. – М.: Мир, 1980.
^* Сибуя М., Ямамото Т. Алгоритмы обработки данных. – М: Мир, 1986. – 218 с.
^* Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. – М.: Наука, 1987.
^* Харари Ф. Теория графов. – М: Мир, 1973.

^* - имеются в наличии в библиотеке СПбГУАП.

Русскоязычные ресурсы InterNet

http://algo.4u.ru/
http://algolist.manual.ru/
http://alglib.chat.ru/
http://algo.do.ru/
http://hcinsu.chat.ru/
http://algolist.da.ru/
http://progstone.narod.ru/links/wantalgo.html
http://www.sevmashvtuz.edu/links/algorithms.html

_______________________________________________________________

Лицензия ЛР №020341 от 07.05.97 г.

Подписано к печати Формат 60х84 1/16 Бумага тип №3

Печать офсетная Усл. печ. л Тираж ___ экз.

_______________________________________________________________

Редакционно-издательский отдел

Отдел оперативной полиграфии СПбГУАП

Содержание