Алгоритмы поиска остовного дерева Прима и Крускала (стр. 1 из 2)
Министерство образования и науки Украины
Сумский государственный университет
Кафедра Информатики
Курсовая работа
по дисциплине
“Теория алгоритмов и математическая логика”
на тему:
“Алгоритмы поиска остовного дерева Прима и Крускала”
Сумы 2006
Содержание
Задание
Вступление
1. Теоретическаячасть
2. Практическаяреализация
Вывод
Программный код
Литература
Задание
Разработать программную реализацию решения задачи о минимальном покрывающем дереве (построение минимального остова). Для нахождения минимального покрывающего дерева использовать алгоритмы Прима и Крускала.
Исходная информация о ребрах графа находится в текстовом файле dan.txt.
Вступление
Пусть имеется связный неориентированный граф G = (V, Е), в котором V— множество контактов, а E — множество их возможных попарных соединений. Для каждого ребра графа (u, v) задан вес w(u, v) (длина провода, необходимого для соединения uи v). Задача состоит в нахождении подмножества Т
Е, связывающего все вершины, для которого суммарный вес минимален.w(T) =
w(u,v)Такое подмножество Т будет деревом (поскольку не имеет циклов: в любом цикле один из проводов можно удалить, не нарушая связности). Связный подграф графа G, являющийся деревом и содержащий все его вершины, называют покрывающим деревом этого графа. (Иногда используют термин "остовное дерево"; для краткости мы будем говорить просто "остов".)
Далее мы рассмотрим задачу о минимальном покрывающем дереве. (Здесь слово "минимальное" означает "имеющее минимально возможный вес".)
Рис 1
На Рис 1 показано на примере минимальное покрывающее дерево. На каждом ребре графа указан вес. Выделены ребра минимального покрывающего дерева (суммарный вес 37). Такое дерево не единственно: заменяя ребро (Ь, с) ребром (а,h), получаем другое дерево того же веса 37.
Мы рассмотрим два способа решения задачи о минимальном покрывающем дереве: алгоритмы Крускала и Прима. Каждый их них легко реализовать со временем работы O(ElogV), используя обычные двоичные кучи. Применив фибоначчиевы кучи, можно сократить время работы алгоритма Прима до O(E+VlogV) (что меньше Е logV, если |V| много меньше \Е\).
Оба алгоритма следуют "жадной" стратегии: на каждом шаге выбирается "локально наилучший" вариант. Не для всех задач такой выбор приведёт к оптимальному решению, но для задачи о покрывающем дереве это так. Здесь будет описана общая схема алгоритма построения минимального остова (добавление рёбер одного за другим). В дальнейшем будут указаны две конкретных реализации общей схемы.
Итак, пусть дан связный неориентированный граф G = (V, Е) и весовая функция w: Е
. Мы хотим найти минимальное покрывающее дерево (остов), следуя жадной стратегии.Общая схема всех наших алгоритмов будет такова. Искомый остов строится постепенно: к изначально пустому множеству А на каждом шаге добавляется одно ребро. Множество А всегда является подмножеством некоторого минимального остова. Ребро (u, v), добавляемое на очередном шаге, выбирается так, чтобы не нарушить этого свойства: А
{(u, v)} тоже должно быть подмножеством минимального остова. Мы называем такое ребро безопасным ребром для А.Generic-MST(G,w)
1 А
2 whileA не является остовом
3 do найти безопасное ребро (u,v) для А
4 А
A {(u,v)}5 return A
Рис. 2. Два изображения одного и того же разреза графа с Рис 1.
(а) Вершины множества S изображены чёрными, его дополнения V\S — белым. Рёбра, пересекающие разрез, соединяют белые вершины с черными. Единственное лёгкое ребро, пересекающее разрез — ребро (d, с). Множество А состоит из серых ребер. Разрез (s, V \S) согласован с А (ни одно ребро из А не пересекает разрез).
(Ь) Вершины множества S изображены слева, вершины V \ S — справа. Ребро пересекает разрез, если оно пересекает вертикальную прямую.
По определению безопасного ребра свойство "А является подмножеством некоторого минимального остова" (для пустого множества это свойство, очевидно, выполнено) остаётся истинным для любого числа итераций цикла, так что в строке 5 алгоритм выдаёт минимальный остов. Конечно, главный вопрос в том, как искать безопасное ребро в строке 3. Такое ребро существует (если А является подмножеством минимального остова, то любое ребро этого остова, не входящее в А, является безопасным). Заметим, что множество А не может содержать циклов (поскольку является частью минимального остова). Поэтому добавляемое в строке 4 ребро соединяет различные компоненты графа Ga= (V,A), и с каждой итерацией цикла число компонент уменьшается на 1. Вначале каждая точка представляет собой отдельную компоненту; в конце весь остов — одна компонента, так что цикл повторяется |V| — 1 раз.
Теоретическая часть
Алгоритм Крускала
В любой момент работы алгоритма Крускала множество А выбранных рёбер (часть будущего остова) не содержит циклов. Оно соединяет вершины графа в несколько связных компонент, каждая из которых является деревом. Среди всех рёбер, соединяющих вершины из разных компонент, берётся ребро наименьшего веса. Надо проверить, что оно является безопасным.
Пусть (u, v) — такое ребро, соединяющее вершины из компонент С1 и C2- Это ребро является лёгким ребром для разреза (С1, V\C1).
Реализация алгоритма Крускала использует структуры данных для непересекающихся множеств. Элементами множеств являются вершины графа. Напомним, что Find-Set(u) возвращает представителя множества, содержащего элемент u. Две вершины uи vпринадлежат одному множеству (компоненте), если Find-Set(u) = Find-Set(v). Объединение деревьев выполняется процедурой Union. (Строго говоря, процедурам Find-Set и Union должны передаваться указатели на uи v)
MST-Kruskal(G,w)
1 A
2 for каждой вершины v
V[G]3 doMake-Set(v)
4 упорядочить рёбра Е по весам
5 for(u,v)
E (в порядке возрастания веса)6do ifFind-Set(u)
Find-Set(v)7then A := A
{(u,v)}8Union(u,v)
9 returnA
Сначала (строки 1-3) множество А пусто, и есть |V| деревьев, каждое из которых содержит по одной вершине. В строке 4 рёбра из Е упорядочиваются по неубыванию веса. В цикле (строки 5-8) мы проверяем, лежат ли концы ребра в одном дереве. Если да, то ребро нельзя добавить к лесу (не создавая цикла), и оно отбрасывается. Если нет, то ребро добавляется к А (строка 7), и два соединённых им дерева объединяются в одно (строка 8).
Подсчитаем время работы алгоритма Крускала. Будем считать, что для хранения непересекающихся множеств используется метод с объединением по рангу и сжатием путей — самый быстрый из известных. Инициализация занимает время O(V), упорядочение рёбер в строке 4 — O(ElogE). Далее производится O(Е) операций, в совокупности занимающих время О(Е
(Е, V)). (основное время уходит на сортировку).Алгоритм Прима
Как и алгоритм Крускала, алгоритм Прима следует общей схеме алгоритма построения минимального остова. В этом алгоритме растущая часть остова представляет собой дерево (множество рёбер которого есть А). Формирование дерева начинается с произвольной корневой вершины r. На каждом шаге добавляется ребро наименьшего веса среди рёбер соединяющих вершины этого дерева с вершинами не из дерева. По следствию такие рёбра являются безопасными для А, так что в результате получается минимальный остов.
При реализации важно быстро выбирать лёгкое ребро. Алгоритм получает на вход связный граф Gи корень r минимального покрывающего дерева. В ходе алгоритма все вершины, ещё не попавшие в дерево, хранятся в очереди с приоритетами. Приоритет вершины vопределяется значением key[u], которое равно минимальному весу рёбер, соединяющих vс вершинами дерева А. (Если таких рёбер нет, полагаем key[V] =
). Поле 
[v] для вершин дерева указывает на родителя, а для вершины v Qуказывает на вершину дерева, в которую ведёт ребро веса key[v] (одно из таких рёбер, если их несколько). Мы не храним множество А вершин строимого дерева явно; его можно восстановить какA = {(v,
[v]):v V\{r} \Q}.В конец работы алгоритма очередь Qпуста, и множество
A = {(v,
[v]):v V\{r}}.