Главная » Java, Структуры данных и алгоритмы » Алгоритм Крускала

0

Утверждение 12.17 является основой построения остовного дерева наименьшего размера. В алгоритме Крускала это используется для создания остовного дерева наименьшего размера в отдельных кластерах. Изначально каждый узел находится в своем кластере. Алгоритм поочередно рассматривает каждый путь в порядке возрастания его веса. Если путь е соединяет два разных кластера, то е добавляется в множество путей остовного дерева, а два кластера, соединенные этим путем, сливаются в один. Если же е связывает два узла, уже расположенные в одном кластере, то е удаляется. Как только алгоритм получает достаточное количество путей для формирования остовного дерева, он завершает свою работу и выдает в качестве результата остовное дерево наименьшего размера.

Псевдокод алгоритма Крускала приводится во фрагменте кода 12.17, а порядок его работы показан на рис. 12.19, 12.20, 12.21.

Алгоритм Kruskal((/):

Input: простой связный взвешенный граф G из п узлов и m путей.

Output: остовное дерево наименьшего размера Гдля G.

for каждого узла v в G do

определить простейший кластер C(v) <- {v}. Инициировать очередь с приоритетами О для размещения всех путей в G, пользуясь весами в качестве ключей. Г <- 0 {Т будет содержать все пути MST} while Т содержит менее чем п – 1 путей do <- Q.removeMin()

Пусть С(\/) будет кластером, содержащим v, а С(и) будет кластером, содержащим и.

if C(v) ф C(u) then

Добавить путь (v,u) в Т. Объединить C(v) и С(и\ в один кластер, return дерево Т

Фрагмент кода 12.17. для решения MST-задачи

Рис. 12.19. в графе, где вес выражен целыми числами. Кластеры показаны’ в виде крупнозаштрихованных участков, а претенденты на рассмотрение в следующей итерации — в виде мелкоза- штрихованных областей. Продолжение — рис. 12:20

Рис. 12.20. в графе (продолжение). Отвергнутые пути выделены пунктиром. Продолжение — рис. 12.21

Достоверность алгоритма Крускала проистекает из ключевого свойства остовного дерева наименьшего размера, определенного утверждением 12.17. Каждый раз, когда алгоритм добавляет путь (v,u) в остовное дерево Г, множество узлов из ^разбивается на кластер V\, содержащий v, и кластер содержащий остальные узлы V. Это однозначно определяет непе-

Рис. 12.21. в графе (продолжение). Путь, рассмотренный в («), сливает два последних кластера, в результате чего выполнение алгоритма завершается

ресекающееся подмножества узлов в К и, что гораздо важнее, поскольку пути из Q выбираются в порядке веса, е должен иметь наименьший вес и одну конечную точку в V\, а другую в Таким образом, алгоритм Крускала всегда добавляет правильное ребро остовного дерева наименьшего размера.

Время выполнения алгоритма Крускала

Проанализируем время выполнения алгоритма Крускала. Обозначим количество узлов и путей в Скак пит соответственно. Будем исходить из того, что вес путей оценивается за постоянный промежуток времени. Рассмотрим более детально структуры данных для реализации алгоритма.

Для реализации приоритетной очереди воспользуемся пирамидой. Таким образом, Q инициируется за 0(т log т) времени повторяющимися вводами или за 0(т) времени с помощью структуры восходящего построения пирамиды (см. п. 7.3.5). Удаление пути с наименьшим весом в каждой итерации while-цикла происходит за 0(log т) времени, что в принципе равно 0(log п), поскольку используется простой граф.

Каждый кластер С представлен неупорядоченным списком узлов, которые могут быть реализованы, например, связными списками; Вместе с каждым узлом v хранится ссылка на его кластер C(v). При такой реализации проверка С(и) ф C(v) занимает 0(1) времени. При слиянии двух кластеров С(и) и C(v) элементы меньшего кластера переносятся в больший с обновлением кластерных ссылок узлов в меньшем кластере. Поскольку можно просто добавить элементы меньшего кластера в конец списка большего кластера, слияние кластеров займет время, пропорциональное размеру меньшего кластера. То есть слияние кластеров С(и) и C(v) займет 0(min{|C(w)|,|C(v)|} времени. < v

Утверждение 12.18. При выполнении алгоритма Крускала в графе из . п узлов и т путей, где кластеры представлены последовательностями и ссылками на кластеры в каждом узле, общее время слияния кластеров есть 0(п log п).

Доказательство. Каждый раз, когда узел переносится в новый кластер, размер кластера, содержащего узел, как минимум удваивается. Пусть t(v) будет количеством передвижений узла в новый кластер. Поскольку максимальный размер кластера составляет п, то t(v) < log/7. Общее время на слияние кластеров в алгоритме Крускала можно получить суммированием времени работы в каждом узле, что пропорционально

Используя утверждение 12.18 и доказательство, сходное с приведенным для алгоритма Дейкстры, приходим к выводу, что общее время выполнения алгоритма Крускала составляет 0((п + m)log я), что можно упростить до 0(т log п), поскольку рассматривается простой связный граф.

Утверждение 12.19. Имея простой связный взвешенный граф G из п узлов и т путей, алгоритм Крускала выстраивает остовное дерево наименьшего размера для G за 0(т log п) времени.

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии