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

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

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

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

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

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

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

на тему:

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

Сумы 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)}

8 Union(u,v)

9 return A

Сначала (строки 1-3) множество А пусто, и есть |V| деревьев, каждое из которых содержит по одной вершине. В строке 4 рёбра из Е упорядочиваются по неубыванию веса. В цикле (строки 5-8) мы проверяем, лежат ли концы ребра в одном дереве. Если да, то ребро нельзя добавить к лесу (не создавая цикла), и оно отбрасывается. Если нет, то ребро добавляется к А (строка 7), и два соединённых им дерева объединяются в одно (строка 8).

Подсчитаем время работы алгоритма Крускала. Будем считать, что для хранения непересекающихся множеств используется метод с объединением по рангу и сжатием путей — самый быстрый из известных. Инициализация занимает время O(V), упорядочение рёбер в строке 4 — O(E logE). Далее производится 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}}.

есть множество ребер покрывающего дерева.

MST-Prim(G,W,r)

1 Q V[G]

2 for для каждой вершины u Q

3 do key[u]

4 key[r] 0

5 [r] nil

6 while Q

7do u Extract-Min(Q)

8for для каждой вершины v Adj[u]

9 do if v Q и w(u,v)<key[v]

10 then [v] u

11 key(v) w(u,v)

После исполнения строк 1-5 и первого прохода цикла в строках 6 ‑ 11 дерево состоит из единственной вершины r, все остальные вершины находятся в очереди, и значение key[v] для них равно длине ребра из r в v или , если такого ребра нет (в первом случае [v] = r). Таким образом, выполнен описанный выше инвариант (дерево есть часть некоторого остова, для вершин дерева поле указывает на родителя, а для остальных вершин на "ближайшую" вершину дерева — вес ребра до неё хранится в key[v].

Время работы алгоритма Прима зависит от того, как реализована очередь Q. Если использовать двоичную кучу (7), инициализацию в строках 1-4 можно выполнить с помощью процедуры Build-Heap за время O(V). Далее цикл выполняется \V\ раз, и каждая операция Extract-Min занимает время O(logV), всего O(V logV). Цикл for в строках 8-11 выполняется в общей сложности О(Е) раз, поскольку сумма степеней вершин графа равна 2\Е\. Проверку принадлежности в строке 9 внутри цикла for можно реализовать за время O(1), если хранить состояние очереди ещё и как битовый вектор размера |V|. Присваивание в строке 11 подразумевает выполнение операции уменьшения ключа (Decrease-Key), которая для двоичной кучи может быть выполнена за время O(logV). Таким образом, всего получаем O(V logV + E logV) = O(E logV) — та же самая оценка, что была для алгоритма Крускала.

Однако эта оценка может быть улучшена, если использовать в алгоритме Прима фибоначчиевы кучи, с помощью неё можно выполнять операцию Extract-Min за учётное время O(logV), а операцию Decrease-Key — за (учётное) время O(1). (Нас интересует именно суммарное время выполнения последовательности операций, так что амортизированный анализ тут в самый раз.) Поэтому при использовании фибоначчиевых куч для реализации очереди время работы алгоритма Прима составит O(Е + V logV).

Программная реализация

Реализуем вышеописанные алгоритмы на практике с помощьюDelphi 7.

Данный скрин является подтверждением выполненной работы.

Вывод