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

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

Выдан результат

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

Программа вернется в исходное состояние