Построение минимального остовного дерева графа методом Прима

Пояснительная записка

к курсовому проекту

тема: Построение минимального остовного дерева графа методом Прима

Введение

При проектировании железных дорог, линий электропередачи и других линий коммуникации возникает проблема построения сети с минимальными затратами. В теории графов такая задача успешно решается путем построения минимального остовного дерева неориентированного графа. Данная задача имеет несколько методов решения. Один из них – алгоритм Прима. Суть этого метода заключается в последовательном добавлении к остову минимального, «безопасного» ребра (ребра, которое не образует цикла). В данной работе представлена программа, базирующаяся на алгоритме Прима, которая вычисляет минимальное остовное дерево неориентированного графа и делает визуализацию графа.

1. Историческая справка

Известный алгоритм построения минимального остовного дерева восходит к Войтеху Ярнику (Vojtech Jarnik) (1930). Он больше известен под именем алгоритма Прима (Robert Prim). Р. Прим независимо от Ярника придумал его в 1956 и представил более подробное и детальное описание, чем первооткрыватель. Еще раз этот алгоритм открыл Эдсгер Дейкстра (Edsger Wybe Dijkstra) в 1958 году, но название осталось за Примом, т. к. у Дейкстры уже был алгоритм с его именем (поиск кратчайших путей в ориентированном графе). Этот алгоритм можно отнести к группе алгоритмов, построенных на наращивании дерева: существует только одна нетривиальная компонента (остальные представляют собой одиночные вершины), и она постепенно наращивается добавлением «безопасных» ребер. Время работы алгоритма Джарника-Прима может достигать O (E+VlogV) при использовании фибоначчиевых куч.

Рассмотрим общую схему работы алгоритмов построения минимального остовного дерева с использованием жадной стратегии. Итак, пусть дан связный неориентированный граф G (V; E) c вершинами и весовая функция w: E → R.

Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G, который называется промежуточным остовным лесом. Изначально G состоит из вершин-компонент, не соединенных друг с другом ( деревьев из одной вершины). На каждом шаге в A добавляется одно новое ребро. Граф A всегда является подграфом некоторого минимального остова. Очередное добавляемое ребро e=(u, v) выбирается так, чтобы не нарушить этого свойства: A ∪ {e} тоже должно быть подграфом минимального. Такое ребро называется безопасным.

Вот как выглядит общий алгоритм построения минимального остовного дерева:

MST-GENERIC (G, w)

1: A ← 0

2: while (пока) A не является остовом

3: do найти безопасное ребро (u, v) ∈ E для A

4: A ← A ∪ {(u, v)}

5: return A

По определению A, он должен оставаться подграфом некоторого минимального остова после любого числа итераций. Конечно, главный вопрос состоит в том, как искать безопасное ребро на шаге 3. Понятно, что такое ребро всегда существует, если A еще не является минимальным остовом (любое ребро остова, не входящее в A). Заметим, что так как A не может содержать циклов, то на каждом шаге ребром соединяются различные компоненты связности (изначально все вершины в отдельных компонентах, в конце A – одна компонента). Таким образом цикл выполняется (n-1) раз.

Далее приводится общее правило отыскания безопасных ребер. Для этого доказана теорема, которая поможет находить безопасные ребра. Предварительно докажем маленькую лемму:

Лемма: пусть Т – минимальное остовное дерево. Тогда любое ребро е из T – безопасное.

Док-во: в Т – (n-1) ребро. На каждом шаге Generic-MST мы добавляли одно безопасное ребро. Всего выполнено (n-1) шагов, следовательно, все ребра в T – безопасные по определению.

Теорема: Пусть G (V; E) – связный неориентированный граф и на множестве Е определена весовая функция w. Пусть А – некоторый подграф G, являющийся в то же время подграфом некоторого минимального остовного дерева T. Рассмотрим компоненту связности К из А. Рассмотрим множество E(K) ребер графа G, только один конец которых лежит в К. Тогда ребро минимального веса из E(K) будет безопасным.
Док-во: Пусть e=(u, v) – минимальное по весу ребро из E(K). Пусть минимальный остов T не содержит e (в противном случае доказываемое утверждение очевидно по приведенной выше лемме). Т.к. T связен, в нем существует некоторый (единственный) ациклический путь из u в v, и e замыкает его в цикл. Поскольку один из концов e лежит в K, а другой в V \ K, в пути существует хотя бы одно ребро e'=(x, y), которое обладает тем же свойством. Это ребро не лежит в A, т. к. в A пока что нет ребер между K и V \ K. Удалим из T ребро e' и добавим e. Так как w(e') < w(e), мы получим остовное дерево T', суммарный вес которого меньше суммарного веса T. Таким образом, T не является минимальным остовом. Противоречие. Следовательно, T содержит e.

В связи с приведенной теоремой введем следующее

Определение. Безопасным ребром e относительно некоторой компоненты связности К из А назовем ребро с минимальным весом, ровно один конец которого лежит в К.

Как и алгоритм Краскала, алгоритм Прима следует общей схеме алгоритма построения минимального остовного дерева: на каждом шаге мы добавляем к строящемуся остову безопасное ребро. Алгоритм Прима относится к группе алгоритмов наращивания минимального остова: на каждом шаге существует не более одной нетривиальной (не состоящей из одной вершины) компоненты связности, и каждый к ней добавляется ребро наименьшего веса, соединяющее вершины компоненты с остальными вершинами. По теореме такое ребро является безопасным.

При реализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться очередью с приоритетами (кучей). Алгоритм получает на вход граф G и его корень r – вершина, на которой будет наращиваться минимальный остов. Все вершины G, еще не попавшие в дерево, хранятся в очереди с приоритетом Ω. Приоритет вершины v определяется значением key(v), которое равно минимальному весу ребер, соединяющих v с вершинами минимального остова. Поле p(v) для вершин дерева указывает на родителя, а для вершин из очереди, указывает на ноду дерева, в которою ведет ребро с весом key(v) (одно из таких ребер, если их несколько).

Тогда алгоритм Прима выглядит следующим образом:

MST-PRIM (G, w, r)

1: Ω ← V(G)

2: foreach (для каждой) вершины u ∈ Ω

3: do key(u) ← ∞

4: key(r) ← 0

5: p(r) = NIL

6: while (пока) Ω ≠ 0

7: do u ← EXTRACT-MIN(Ω)

8: foreach (для каждой) вершины v ∈ Adj(u)

9: do if v ∈ Ω и w (u, v) < key(v) then

10: p(v) ← u

11: key(v) ← w (u, v)

На рисунках 1–8 показана схема работы алгоритма Прима с корнем r.

Рисунок 1 – Начальная фаза. Минимальный покрывающий лес состоит из корня и пустого множества ребер

Рисунок 2 – Ребро с весом 6 является минимальным ребро, соединяющим корень с остальными вершинами. Добавляем его к минимальному остову.

Рисунок 3 – Следующее безопасное ребро с весом 11. Добавляем его

Рис. 4

Рисунок 5

Рисунок 6

Рисунок 7

Рисунок 8 – Ребра с весом 17, 19 и 25 – не безопасные. Их концы лежат в одной компоненте связности. Ребро с весом 21 – безопасное, поэтому добавляем его. Минимальное остовное дерево построено.

Время работы алгоритма Прима зависит от того, как реализована очередь с приоритетами Ω. Если использовать двоичную кучу, инициализацию в строках 1–4 можно выполнить за время O(V). Далее цикл выполняется |V| раз, и каждая операция EXTRACT-MIN занимает время O(VlogV). Цикл for в строках 8–11 выполняется в общей сложности O(E), поскольку сумма степеней вершин графа равна 2|E|. Проверку принадлежности в строке 9 можно выполнить за время O(1), если хранить состояние очереди еще и как битовый вектор размера |V|. Присваивание в строке 11 подразумевает выполнение операции уменьшения ключа (DECREASE-KEY), которая для двоичной кучи может быть выполнена за время O(logV). Таким образом всего получаем O (VlogV+ElogV)=O(ElogV).

Лучшую оценку можно получить, если использовать фибоначчиевы кучи. С помощью фибоначчиевых куч можно выполнить операцию EXTRACT-MIN за учетное время O(logV), а операцию DECREASE-KEY – за учетное время O(1). В этом случае суммарное время работы алгоритма Прима составит O (E+VlogV).

алгоритм остовной дерево программа

Интерфейс программы (приложение А, В) должен быть следующим. Сначала пользователь вводит порядок графа, чтобы программа могла сформировать таблицу ввода данных (матрица весов) с соответствующим количеством строк и столбцов. При этом все кнопки, кроме кнопки «Сделать таблицу» недоступны для пользователя. Затем пользователь вводит в таблицу данные, при этом он может оставлять пустые ячейки в таблице. Программа будет интерпретировать это как отсутствие ребра между вершинами. Когда данные будут введены, нужно нажать на кнопку «Рассчитать дерево», которая после создания программой таблицы станет активной. Программа рассчитает матрицу весов для минимального остовного дерева и нарисует искомый граф (длины ребер графа не будут соответствовать матрице весов). При этом таблица ввода и все кнопки, кроме кнопки «Продолжить», станут недоступны для пользователя. При нажатии на эту единственную активную кнопку программа перейдет в исходное состояние.

Теперь о том, как программа реализует алгоритм Прима.

Сначала программа создает некий массив a(10) (10) (предполагается, что число вершин графа меньше или равно 10). Этот массив инициализируется: каждому a(i) (j) присваивается 1000 (предполагается, что максимальная длина ребра меньше 1000). Потом данные из таблицы ввода копируются в массив. При этом если в ячейке таблицы ничего не содержится в массив ничего не копируется. Затем делается цикл, который прерывается только тогда, когда все элементы массива станут снова равны 1000. Как работает цикл? Сначала находится минимальный элемент массива (из области выше главной диагонали матрицы ввода). Он запоминается (переменная buf) и ему присваивается 1000. Согласно алгоритму Прима, если ребро подходящее минимальный элемент вычеркивается, а цикл начинается с начала. Подходящее ребро или нет? Ответ на этот вопрос находится следующим образом. Создается массив в n элементов. Каждый элемент равен 1 или 0. Когда вершина включается в дерево, в элемент массива с ее номером записывается 1 (изначально все элементы массива, кроме первого равны 0). Чтобы определить подходящее ребро или нет, нужно посмотреть, находятся ли единицы в массиве (номера элементов равны номерам вершин ребра). Если номерам вершин ребра соответствуют обе единица, значит, ребро не подходящее. Если это условие не выполняется – ребро подходящее. Алгоритм прекращает работу, когда все вершины включены в новый граф.

Отдельно можно выделить процедуру рисования графа. Программа создает двумерный массив координат вершин графа (krug (2) (10)). Вершины располагаются на окружности на одинаковом расстоянии друг от друга. Такой способ очень удобный, потому что не надо беспокоиться о том, что ребра будут наслаиваться одно на другое.

5. Тестирование программы

Тестирование программы проводилось на самых разных вариантах матрицы весов. В процессе тестирования ошибок не обнаружено.

Программа тестировалась на следующих примерах:

Матрица весов