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

Содержание

Задание

Вступление

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)}

--> ЧИТАТЬ ПОЛНОСТЬЮ <--