Трассировка межсоединений

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


2.Практическая часть
2.1.Описание работы выданного алгоритма
На рис. 2.1 приведена схема алгоритма Прима.

Рис. 2.1 – Блок-схема алгоритма Прима
2.2. Тестирование работы программы
Входной информацией для программы является матрица весов графа. Выходной информацией является матрица связности минимального остовного дерева.
Тестовый набор N1
Матрица весов
1 2 3 4 5 6 1 - 1 2 4 4 6 2 - 3 6 5 2 3 - 3 4 3 4 - 5 6 5 - 2 6 -
Результат
1 2 3 4 5 6 1 - 1 2 2 - 2 3 - 3 4 - 5 - 2 6 -
Тестовый набор N2
Матрица весов
1 2 3 4 5 6 1 - 5 2 4 7 1 2 - 4 3 3 2 3 - 3 5 6 4 - 5 2 5 - 7 6 -
Результат
1 2 3 4 5 6 1 - 2 1 2 - 3 2 3 - 4 - 2 5 - 6 -
Тестовый набор N3
Матрица весов
1 2 3 4 5 6 7 8 9 10 1 - 4 5 9 2 - 3 - 8 4 - 7 7 7 5 - 5 6 - 4 7 - 8 - 6 9 - 10 -
Результат
1 2 3 4 5 6 7 8 9 10 1 - 4 5 9 2 - 3 - 8 4 - 7 7 5 - 5 6 - 4 7 - 8 - 6 9 - 10 -
2.2.Инструкция пользователя
После запуска приложения появляется главное окно программы построения минимального оставного дерева.

Вводим в текстовое поле количество вершин графа и нажимаем кнопку «Рассчитать». Программа строит матрицы размерности заданной пользователем.

Далее заполняем матрицу весов для графа заданного размера и нажимаем кнопку «Рассчитать».

Построение графа идет поэтапно, на каждом ребре графа выводится информационное сообщение.















Конец работы программы граф построен. В правой таблице заполнена матрица весов минимального остова графа.

Список литературы
Бахвалов Н.С., Жидков Н.П., Кобельков Г.М. Численные методы. (М.: Наука, 2007. -598 с.
Бахвалов Н.С. Численные методы. Часть 1. (М.: Наука, 2003. (631 с.
Самарский А.А. Введение в численные методы. (М.: Наука, 2002. (286 с.
Калиткин Н.Н. Численные методы. (М.: Наука, 2006. (512 с.
Крылов В.И., Бобков В.В., Монастырный П.И. Вычислительные методы. Т. I, II. (М.: Наука, 2007. (600 с.
Житников В.П., Шерыхалина Н.М., Ураков А.Р. Линейные некорректные задачи. Верификация численных результатов. Учебное пособие. (Уфа: УГАТУ, 2002. (91 с.
Smith D.A., Ford W.F. Acceleration of linear and logarithmic convergence. – SIAM J. Numer. Anal., 2009, v. 16. (P. 223-240.
Smith D. A., Ford W. F. Numerical comparisons of non-linear convergence accelerations. – Mathematics of Computation, 2002, v. 38, 158. (P. 481–499.
Прудников А.П., Бычков Ю.А., Маричев О.И. Интегралы и ряды. –М.: Наука, 1981. (800 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы. — М.: Видавничий будинок «Вільямс», 2001.
Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2001
Н. Кристофидес, Теория графов– «Мир» Москва, 2008
Приложение – исходный код программы
//---------------------------------------------------------------------------
#include
#pragma hdrstop

#include "Unit1.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; iversh[i]=0;
versh[1]=1;
for(int i=0; ifor(int j=0; ja[i][j]=1000;
//*******
for(int i=0; ifor(int j=0; jif (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; ifor(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]);
//**********
//рисование
int krug[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]]);
MessageBox(NULL, "Продолжить построение", "Построение остова", MB_OK);
}
}
//---------------------------------------------------------------------------
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);
}
//---------------------------------------------------------------------------









6