Таким образом всего получаем 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.
S mith D. A., F ord W.
F. N umerical comparisons of non-linear convergence accelerations. — M athematics 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; 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]);
//**********
int k=n-1;
while (k≠0)
{
int buf=1000;
int x, 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]);
//**********
//рисование
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);
}
//—————————————————————————————————————;
