Алгоритмы поиска остовного дерева Прима и Крускала

Министерство образования и науки Украины

Сумский государственный университет

Кафедра Информатики

Курсовая работа

по дисциплине

“Теория алгоритмов и математическая логика”

на тему:

“Алгоритмы поиска остовного дерева Прима и Крускала”

Сумы 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(E logV), используя обычные двоичные кучи. Применив фибоначчиевы кучи, можно сократить время работы алгоритма Прима до O(E+V logV) (что меньше Е logV, если |V| много меньше \Е\).

Оба алгоритма следуют "жадной" стратегии: на каждом шаге выбирается "локально наилучший" вариант. Не для всех задач такой выбор приведёт к оптимальному решению, но для задачи о покрывающем дереве это так. Здесь будет описана общая схема алгоритма построения минимального остова (добавление рёбер одного за другим). В дальнейшем будут указаны две конкретных реализации общей схемы.

Итак, пусть дан связный неориентированный граф G = (V, Е) и весовая функция w: Е. Мы хотим найти минимальное покрывающее дерево (остов), следуя жадной стратегии.

Общая схема всех наших алгоритмов будет такова. Искомый остов строится постепенно: к изначально пустому множеству А на каждом шаге добавляется одно ребро. Множество А всегда является подмножеством некоторого минимального остова. Ребро (u, v), добавляемое на очередном шаге, выбирается так, чтобы не нарушить этого свойства: А{(u, v)} тоже должно быть подмножеством минимального остова. Мы называем такое ребро безопасным ребром для А.

Generic-MST(G,w)

1 А

2 while A не является остовом

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 ребро соединяет различные компоненты графа G_a = (V,A), и с каждой итерацией цикла число компонент уменьшается на 1. Вначале каждая точка представляет собой отдельную компоненту; в конце весь остов — одна компонента, так что цикл повторяется |V| — 1 раз.

Теоретическая часть

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

В любой момент работы алгоритма Крускала множество А выбранных рёбер (часть будущего остова) не содержит циклов. Оно соединяет вершины графа в несколько связных компонент, каждая из которых является деревом. Среди всех рёбер, соединяющих вершины из разных компонент, берётся ребро наименьшего веса. Надо проверить, что оно является безопасным.

Пусть (u, v) — такое ребро, соединяющее вершины из компонент С₁ и C₂- Это ребро является лёгким ребром для разреза (С₁, V \C₁).

Реализация алгоритма Крускала использует структуры данных для непересекающихся множеств. Элементами множеств являются вершины графа. Напомним, что 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 do Make-Set(v)

4 упорядочить рёбра Е по весам

5 for (u,v)  E (в порядке возрастания веса)

6 do if Find-Set(u)  Find-Set(v)

7 then A := A{(u,v)}