Название: Построение минимального остовного дерева графа методом Прима
Вид работы: курсовая работа
Рубрика: Математика
Размер файла: 83.16 Kb
Скачать файл: referat.me-215962.docx
Краткое описание работы: Алгоритм построения минимального остовного дерева, история его формирования. Построение минимального остовного дерева. Алгоритм Прима, его содержание и назначение. Порядок составления и тестирования программы, ее интерфейс и правила эксплуатации.
Построение минимального остовного дерева графа методом Прима
Пояснительная записка
к курсовому проекту
тема: Построение минимального остовного дерева графа методом Прима
Введение
При проектировании железных дорог, линий электропередачи и других линий коммуникации возникает проблема построения сети с минимальными затратами. В теории графов такая задача успешно решается путем построения минимального остовного дерева неориентированного графа. Данная задача имеет несколько методов решения. Один из них – алгоритм Прима. Суть этого метода заключается в последовательном добавлении к остову минимального, «безопасного» ребра (ребра, которое не образует цикла). В данной работе представлена программа, базирующаяся на алгоритме Прима, которая вычисляет минимальное остовное дерево неориентированного графа и делает визуализацию графа.
1. Историческая справка
Известный алгоритм построения минимального остовного дерева восходит к Войтеху Ярнику (Vojtech Jarnik) [1930]. Он больше известен под именем алгоритма Прима (Robert Prim). Р. Прим независимо от Ярника придумал его в 1956 и представил более подробное и детальное описание, чем первооткрыватель. Еще раз этот алгоритм открыл Эдсгер Дейкстра (Edsger Wybe Dijkstra) в 1958 году, но название осталось за Примом, т. к. у Дейкстры уже был алгоритм с его именем (поиск кратчайших путей в ориентированном графе). Этот алгоритм можно отнести к группе алгоритмов, построенных на наращивании дерева: существует только одна нетривиальная компонента (остальные представляют собой одиночные вершины), и она постепенно наращивается добавлением «безопасных» ребер. Время работы алгоритма Джарника-Прима может достигать O (E+VlogV) при использовании фибоначчиевых куч.
2. Построение минимального остовного дерева
Рассмотрим общую схему работы алгоритмов построения минимального остовного дерева с использованием жадной стратегии. Итак, пусть дан связный неориентированный граф G (V ; E ) c n вершинами и весовая функция w : E → R .
Искомый остов строится постепенно. Алгоритм использует некоторый ациклический подграф А исходного графа G , который называется промежуточным остовным лесом . Изначально G состоит из n вершин-компонент, не соединенных друг с другом (n деревьев из одной вершины). На каждом шаге в 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
связен, в нем существует некоторый (единственный) ациклический путь p
из u
в v
, и e
замыкает его в цикл. Поскольку один из концов e
лежит в K
, а другой в V
K
, в пути p
существует хотя бы одно ребро e'
=(x
, y
), которое обладает тем же свойством. Это ребро не лежит в A
, т. к. в A
пока что нет ребер между K
и V
K
. Удалим из T
ребро e'
и добавим e
. Так как w
(e'
) < w
(e
), мы получим остовное дерево T'
, суммарный вес которого меньше суммарного веса T
. Таким образом, T
не является минимальным остовом. Противоречие. Следовательно, T
содержит e
.
В связи с приведенной теоремой введем следующее
Определение. Безопасным ребром e относительно некоторой компоненты связности К из А назовем ребро с минимальным весом, ровно один конец которого лежит в К.
3. Алгоритм Прима
Как и алгоритм Краскала, алгоритм Прима следует общей схеме алгоритма построения минимального остовного дерева: на каждом шаге мы добавляем к строящемуся остову безопасное ребро. Алгоритм Прима относится к группе алгоритмов наращивания минимального остова: на каждом шаге существует не более одной нетривиальной (не состоящей из одной вершины) компоненты связности, и каждый к ней добавляется ребро наименьшего веса, соединяющее вершины компоненты с остальными вершинами. По теореме такое ребро является безопасным.
При реализации надо уметь на каждом шаге быстро выбирать безопасное ребро. Для этого удобно воспользоваться очередью с приоритетами (кучей). Алгоритм получает на вход граф 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(V logV ). Цикл for в строках 8–11 выполняется в общей сложности O(E ), поскольку сумма степеней вершин графа равна 2|E |. Проверку принадлежности в строке 9 можно выполнить за время 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 (E +V logV ).
4. Составление программы
алгоритм остовной дерево программа
Интерфейс программы (приложение А, В) должен быть следующим. Сначала пользователь вводит порядок графа, чтобы программа могла сформировать таблицу ввода данных (матрица весов) с соответствующим количеством строк и столбцов. При этом все кнопки, кроме кнопки «Сделать таблицу» недоступны для пользователя. Затем пользователь вводит в таблицу данные, при этом он может оставлять пустые ячейки в таблице. Программа будет интерпретировать это как отсутствие ребра между вершинами. Когда данные будут введены, нужно нажать на кнопку «Рассчитать дерево», которая после создания программой таблицы станет активной. Программа рассчитает матрицу весов для минимального остовного дерева и нарисует искомый граф (длины ребер графа не будут соответствовать матрице весов). При этом таблица ввода и все кнопки, кроме кнопки «Продолжить», станут недоступны для пользователя. При нажатии на эту единственную активную кнопку программа перейдет в исходное состояние.
Теперь о том, как программа реализует алгоритм Прима.
Сначала программа создает некий массив a[10] [10] (предполагается, что число вершин графа меньше или равно 10). Этот массив инициализируется: каждому a[i] [j] присваивается 1000 (предполагается, что максимальная длина ребра меньше 1000). Потом данные из таблицы ввода копируются в массив. При этом если в ячейке таблицы ничего не содержится в массив ничего не копируется. Затем делается цикл, который прерывается только тогда, когда все элементы массива станут снова равны 1000. Как работает цикл? Сначала находится минимальный элемент массива (из области выше главной диагонали матрицы ввода). Он запоминается (переменная buf) и ему присваивается 1000. Согласно алгоритму Прима, если ребро подходящее минимальный элемент вычеркивается, а цикл начинается с начала. Подходящее ребро или нет? Ответ на этот вопрос находится следующим образом. Создается массив в n элементов. Каждый элемент равен 1 или 0. Когда вершина включается в дерево, в элемент массива с ее номером записывается 1 (изначально все элементы массива, кроме первого равны 0). Чтобы определить подходящее ребро или нет, нужно посмотреть, находятся ли единицы в массиве (номера элементов равны номерам вершин ребра). Если номерам вершин ребра соответствуют обе единица, значит, ребро не подходящее. Если это условие не выполняется – ребро подходящее. Алгоритм прекращает работу, когда все вершины включены в новый граф.
Отдельно можно выделить процедуру рисования графа. Программа создает двумерный массив координат вершин графа (krug[2] [10]). Вершины располагаются на окружности на одинаковом расстоянии друг от друга. Такой способ очень удобный, потому что не надо беспокоиться о том, что ребра будут наслаиваться одно на другое.
5. Тестирование программы
Тестирование программы проводилось на самых разных вариантах матрицы весов. В процессе тестирования ошибок не обнаружено.
Программа тестировалась на следующих примерах:
Матрица весов
2 | 4 |
3 |
Выдан результат
2 |
3 |
Матрица весов
2 | 3 |
Выдан результат
2 | 3 |
Матрица весов
3 | 5 |
4 | |
1 |
Выдан результат
3 |
4 |
Матрица весов
6 | 5 | 3 |
2 | 5 | |
6 |
Выдан результат
5 | 3 |
2 |
Матрица весов
5 | 6 | 4 | 7 | 8 | 5 |
8 | 5 | 19 | 6 | 9 | |
2 | 8 | 7 | 10 | ||
7 | 3 | 8 | |||
6 | 7 | ||||
5 |
Выдан результат
5 | 4 | 5 |
2 | ||
3 | ||
6 |
На рисунке 9 изображен результат работы программы
Рисунок 9 – Окно программы
Заключение
В ходе проделанной работы была написана программа, реализующая алгоритм Прима. В результате программа выдает матрицу весов минимального остовного дерева графа, и изображает полученный граф.
Список использованных источников
1. http://works.tarefer.ru
2. http://www.intuit.ru
3. http://www.offzone.litehosting.ru
Приложение А
Листинг программы
// –
#include <vcl.h>
#pragma hdrstop
#include «Unit21.h»
// –
#pragma package (smart_init)
#include «math.h»
#pragma resource «*.dfm»
TForm1 *Form1;
int n=3;
// –
__fastcall TForm1:TForm1 (TComponent* Owner)
: TForm(Owner)
{
}
// –
void __fastcall TForm1: Button1Click (TObject *Sender)
{
n=StrToInt (Edit1->Text);
StringGrid1->ColCount=n;
StringGrid1->RowCount=n;
StringGrid2->ColCount=n;
StringGrid2->RowCount=n;
StringGrid1->Visible=true;
BitBtn1->Enabled=true;
Button1->Enabled=false;
}
// –
void __fastcall TForm1: BitBtn1Click (TObject *Sender)
{
BitBtn2->Enabled=true;
BitBtn1->Enabled=false;
Button1->Enabled=false;
StringGrid2->Visible=true;
int a[10] [10];
int mas[3] [10];
int kmas=0;
int versh[10];
for (int i=0; i<n; i++)
versh[i]=0;
versh[1]=1;
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
a[i] [j]=1000;
// *******
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
if (StringGrid1->Cells[i] [j]!=»») a[i] [j]=StrToInt (StringGrid1->Cells[i] [j]);
// **********
int k=n-1;
while (k!=0)
{
int buf=1000;
int x, y;
for (int i=1; i<n; i++)
for (int j=0; j<i; j++)
{
if ((a[i] [j]<buf) && ((versh[i]==1) || (versh[j]==1)) && (versh[i]!=versh[j]))
{buf=a[i] [j]; x=i; y=j;}
}
if (versh[x]==1) versh[y]=1; else versh[x]=1;
a[x] [y]=1000;
mas[0] [kmas]=x;
mas[1] [kmas]=y;
mas[2] [kmas]=buf;
kmas++;
// *****
k –;
}
/// ***********************
for (int i=0; i<kmas; i++)
StringGrid2->Cells [mas[0] [i]] [mas[1] [i]]=IntToStr (mas[2] [i]);
// **********
// рисование
int krug[2] [10];
Form1->Canvas->Pen->Color=clBlack;
for (int i=0; i<n; i++)
{
krug[0] [i]=400+100*sin (6.28*i/n);
krug[1] [i]=400+100*cos (6.28*i/n);
}
for (int i=0; i<kmas; i++)
{
Form1->Canvas->MoveTo (krug[0] [mas[0] [i]], krug[1] [mas[0] [i]]);
Form1->Canvas->LineTo (krug[0] [mas[1] [i]], krug[1] [mas[1] [i]]);
}
}
// –
void __fastcall TForm1: BitBtn2Click (TObject *Sender)
{
Button1->Enabled=true;
StringGrid1->Visible=false;
StringGrid2->Visible=false;
BitBtn2->Enabled=false;
Form1->Canvas->Pen->Color=clBtnFace;
Form1->Canvas->Rectangle (295, 295,505, 505);
}
Программа тестировалась на следующих примерах:
Приложение Б
Инструкция пользователя
Ограничения программы:
– количество вершин графа не более 10;
– длина ребра – целое положительное число, меньше 1000.
Порядок работы:
1) Пользователь вводит количество вершин графа
2) Нажимается кнопка «Сделать таблицу»
3) Вводятся данные в таблицу
4) Нажимается кнопка «Рассчитать дерево»
Программа составляет матрицу весов для минимального остовного дерева и изображает искомый граф.
5) Если пользователь хочет продолжить работу с программой, он должен нажать на кнопку «Продолжить»
Программа вернется в исходное состояние
Похожие работы
-
Двумерная кластеризая по предельному расстоянию. Дискретная математика
Изучение основных вопросов теории графов и области ее применения на практике. Разработка алгоритма кластеризации по предельному расстоянию и построение минимального остовного дерева каждого кластера. Результаты тестирований работы данного алгоритма.
-
Задача о коммивояжере и ее обобщения
Суть задачи коммивояжера, ее применение. Общая характеристика методов ее решения: метод полного перебора, "жадные" методы, генетические алгоритмы и их обобщения. Особенности метода ветвей и границ и определение наиболее оптимального решения задачи.
-
Типовой расчет графов
Данная работа является типовым расчетом по курсу "Дискретная математика" по теме "Графы", предлагаемая студентам МГТУ им. Баумана.
-
Деревья и их свойства (частный вид графов)
Вид графов, используемых в теории электрических цепей, химии, вычислительной технике и в информатике. Основные свойства деревьев. Неориентированный граф. Алгоритм построения минимального каркаса. Обоснование алгоритма. Граф с нагруженными ребрами.
-
Математическая логика и теория алгоритмов
Постановка задачи, построение модели, описание алгоритма описание переменных и программа, расчёт вычислительной сложности.
-
Использование математических методов и моделей в управлении микроэкономическими системами
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ОТКРЫТЫЙ УНИВЕРСИТЕТ
-
Моделирование систем
Составление таблицы значений функции алгебры логики и нахождение всех существенных переменных. Связный ориентированный и взвешенный граф. Построение функции полиномом Жегалкина. Текст программы для алгоритма Дейкстры. Определение единиц и нулей функции.
-
Нахождение минимального остовного дерева алгоритмом Краскала
Минимальное остовное дерево связного взвешенного графа и его нахождение с помощью алгоритмов. Описание алгоритма Краскала, возможность строить дерево одновременно для нескольких компонент связности. Пример работы алгоритма Краскала, код программы.
-
Разработка алгоритмического и программного обеспечения для решения графовых задач
Содержание Содержание 2 Введение 3 Алгоритмы на графах 6 Заключение 21 Литература 24 Приложение 25 Введение Теория графов – это область дискретной математики, особенностью которой является геометрический подход к изучению объектов. Теория графов находится сейчас в самом расцвете. Обычно её относят к топологии (во многих случаях рассматриваются лишь топологические свойства графов), однако она пересекается со многими разделами теории множеств, комбинаторной математики, алгебры, геометрии, теории матриц, теории игр, математической логики и многих других математических дисциплин.
-
Знаходження мінімального остовом дерева. Порівняння алгоритму Прима і алгоритму Крускала
Особливості реалізації алгоритмів Прима та Крускала побудови остового дерева у графі. Оцінка швидкодії реалізованого варіанта алгоритму. Характеристика різних методів побудови остовних дерев мінімальної вартості. Порівняння використовуваних алгоритмів.