Построение минимального остовного дерева графа методом Прима (стр. 2 из 2)
Теперь о том, как программа реализует алгоритм Прима.
Сначала программа создает некий массив 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) Если пользователь хочет продолжить работу с программой, он должен нажать на кнопку «Продолжить»
Программа вернется в исходное состояние