Пояснительная записка
к курсовому проекту
тема: Построениеминимального остовного дерева графа методом Прима
Введение
Припроектировании железных дорог, линий электропередачи и других линийкоммуникации возникает проблема построения сети с минимальными затратами. Втеории графов такая задача успешно решается путем построения минимальногоостовного дерева неориентированного графа. Данная задача имеет несколькометодов решения. Один из них – алгоритм Прима. Суть этого метода заключается впоследовательном добавлении к остову минимального, «безопасного» ребра (ребра,которое не образует цикла). В данной работе представлена программа,базирующаяся на алгоритме Прима, которая вычисляет минимальное остовное деревонеориентированного графа и делает визуализацию графа.
1. Историческая справка
Известныйалгоритм построения минимального остовного дерева восходит к Войтеху Ярнику(Vojtech Jarnik) [1930]. Он больше известен под именем алгоритма Прима (RobertPrim). Р. Прим независимо от Ярника придумал его в 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:dou ← EXTRACT-MIN(Ω)
8: foreach (для каждой) вершины v ∈ Adj(u)
9:doif v ∈ Ω и w (u, v) 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).
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. works.tarefer.ru
2. www.intuit.ru
3. www.offzone.litehosting.ru
Приложение А
Листингпрограммы
//–
#include
#pragmahdrstop
#include«Unit21.h»
//–
#pragmapackage (smart_init)
#include«math.h»
#pragmaresource «*.dfm»
TForm1*Form1;
intn=3;
//–
__fastcallTForm1: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;
inta[10] [10];
intmas[3] [10];
intkmas=0;
intversh[10];
for(int i=0; i
versh[i]=0;
versh[1]=1;
for(int i=0; i
for(int j=0; j
a[i][j]=1000;
//*******
for(int i=0; i
for(int j=0; j
if(StringGrid1->Cells[i] [j]!=»») a[i] [j]=StrToInt (StringGrid1->Cells[i] [j]);
//**********
intk=n-1;
while(k!=0)
{
intbuf=1000;
intx, y;
for(int i=1; i
for(int j=0; j
{
if((a[i] [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
StringGrid2->Cells[mas[0] [i]] [mas[1] [i]]=IntToStr (mas[2] [i]);
//**********
//рисование
intkrug[2] [10];
Form1->Canvas->Pen->Color=clBlack;
for(int i=0; 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
{
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) Еслипользователь хочет продолжить работу с программой, он должен нажать на кнопку«Продолжить»
Программавернется в исходное состояние