Покрывающее дерево или остовной лес минимального веса с помощью алгоритма Солина

Министерство образования Российской Федерации

Государственное образовательное учреждение высшего профессионального образования «Комсомольский - на - Амуре Государственный Технический Университет»

Кафедра МОП ЭВМ

Лабораторная работа  №4

по дисциплине:

Структуры и алгоритмы обработки данных

Вариант 6

Группа:      4ВТ-1

Выполнил:             ПритыченкоС.В.

Проверил: Изабеков З.А.

 2007 г.

Задание.

Найти покрывающее дерево или остовной лес минимального веса с помощью алгоритма Солина. Вершины графа – города. Веса ребер равны ценам билетов.

Текст программы

#include <vcl.h>

#pragma hdrstop

#include "Unit1.h"

#include <math.h>

#include <memory.h>

//--------------------------------------------------------------------------#pragma package(smart_init)

#pragma resource "*.dfm"

int xMax, yMax, id = 0;

TForm1 *Form1;

//--------------------------------------------------------------------------__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//--------------------------------------------------------------------------int i, j;

int N = 0, r = 15, **ways, v1, v2, **arr, *cx, *cy, count;

struct LPoint

{

int x, y;

LPoint *next;

};

struct Vert

{

int n;

Vert *next;

};

LPoint *list = NULL;

Vert **vertex;

void link(int d, int k)

{

int i;

for (i = 0; i < N; ++i)

{

if (i == d)

{

arr[k][i] = arr[i][k] = 0;

continue;

}

if (arr[k][i])

{

arr[i][k] = arr[k][i] = 0;

Vert *p = vertex[d];

while (p->next) p = p->next;

p->next = vertex[i];

vertex[i] = NULL;

link(d, i);

}

}

}

void solin()

{

int sum = 0;      // пееременная для хранения суммы цен билетов

int min, nv1, nv2, m, end = 1;

Vert *v1, *v2;  // переменные для указания вершин, рассматриваемых в данный момент

// count = N - 1;

while (end)

{

end = 0;

for (i = 0; i < N; ++i)

{

m = -1;

v1 = vertex[i];

min = 1000000000;

if (!v1) continue;

while (v1)

{

for (j = 0; j < N; ++j)

{

if (i == j) continue;

v2 = vertex[j];

while (v2)

{

if (ways[v1->n][v2->n] && ways[v1->n][v2->n] < min)      //если есть путь меж. 2 - мя вершинами и он меньше чем мин.

{

m = j; nv1 = v1->n; nv2 = v2->n;  //запоминаем номер второй группы и вершины которые соединяются

min = ways[nv1][nv2];

}

v2 = v2->next;

}

}

v1 = v1->next;

}

if (!arr[i][m] && m != -1)     // Если есть еще отдельные группы и они ещё не связаны

{

Form1->Image1->Canvas->MoveTo(cx[nv1], cy[nv1]);

Form1->Image1->Canvas->LineTo(cx[nv2], cy[nv2]);

arr[i][m] = arr[m][i] = 1;

sum += ways[nv1][nv2];

end = 1;

}

}

for (i = 0; i < N; ++i)

if (vertex[i])

{

link(i, i);

}

}

AnsiString str = sum;

MessageBoxA(NULL, str.c_str(), "Минимальное дерево", 0);

}

void __fastcall TForm1::inputClick(TObject *Sender)       // Нажатие кнопки ввод вершин

{

Form1->List->Clear();

Image1->Canvas->Brush->Color = RGB(255, 255, 255);

Image1->Canvas->Brush->Style = bsSolid;

Image1->Canvas->Pen->Color = RGB(0, 0, 0);

Image1->Canvas->Pen->Width = 1;

Image1->Canvas->Pen->Mode = pmCopy;

Form1->Image1->Canvas->Rectangle(-2, -2, Image1->ClientWidth + 2, Image1->ClientHeight + 2);

N = 0;

LPoint *p;

while (list)

{

p = list;

list = list->next;

delete p;

}

Form1->Image1->Canvas->Brush->Color = RGB(0, 200, 0);

id = 1;

}

//--------------------------------------------------------------------------void __fastcall TForm1::Image1MouseDown(TObject *Sender,       // Нажатие клавиши мыши

TMouseButton Button, TShiftState Shift, int X, int Y)

{

if( id == 1)

{

LPoint *p = new LPoint;

p->next = list; p->x = X; p->y = Y;

list = p;

Image1->Canvas->Ellipse(X - r, Y - r, X + r, Y + r);

Image1->Canvas->TextOutA(X - r / 4, Y - r / 3, N);

++N;

}

if (id == 2)

{

LPoint *p = list;

i = N - 1;

while (p)

{

if (pow(p->x - X, 2) + pow(p->y - Y, 2) <= pow(r, 2)) break;

--i;

p = p->next;

}

if (i >= 0)       // Если было нажатие мышкой на городе

{

if (v1 == -1)

{

v1 = i;

Image1->Canvas->Pen->Mode = pmNot;        // Инверсия окружности

Image1->Canvas->Ellipse(p->x - r - 1, p->y - r - 1, p->x + r + 1, p->y + r + 1);

}

else

{

LPoint *q = list;

for (j = N - 1; j > v1; --j) q = q->next;     // Ищем первую выделенную вершину

ways[i][v1] = ways[v1][i] = StrToInt(InputBox("Цена","Введите цену билета","1"));     // Запоминаем цены билетов

AnsiString str = v1; str.Insert(" - ", str.Length() + 1);str.Insert(i, str.Length() + 1);

str.Insert(" = ", str.Length() + 1); str.Insert(ways[i][v1], str.Length() + 1);

Form1->List->AddItem(str, 0);                   // Вывод информации о ценах в список

Image1->Canvas->Ellipse(q->x - r - 1, q->y - r - 1, q->x + r + 1, q->y + r + 1);

Image1->Canvas->Pen->Mode = pmCopy;

Image1->Canvas->MoveTo(q->x, q->y);       // Рисуем ребро

Image1->Canvas->LineTo(p->x, p->y);

v1 = -1;

}

}

}

}

//--------------------------------------------------------------------------//--------------------------------------------------------------------------void __fastcall TForm1::vertClick(TObject *Sender)        // Задать цены

{

if (id == 1)

{

Image1->Canvas->Pen->Color = RGB(0, 0, 200);

Image1->Canvas->Pen->Width = 2;

Image1->Canvas->Brush->Style = bsClear;

ways = new int *[N];

for (i = 0; i < N; ++i)

{

ways[i] = new int [N];

memset(ways[i], 0, N * sizeof(int));

}

v1 = -1, v2 = -1;

id = 2;

}

}

//--------------------------------------------------------------------------//--------------------------------------------------------------------------void __fastcall TForm1::searchClick(TObject *Sender)

{

if (id == 2)

{

vertex = new Vert *[N];   //массив указателей на списки вершин

cx = new int [N];

cy = new int [N];

LPoint *p = list;

for (i = N - 1; i >= 0; --i)       //запоминаем коор. каждой вершины

{

cx[i] = p->x; cy[i] = p->y;

p = p->next;

}

for (i = 0; i < N; ++i)

{

vertex[i] = new Vert;

vertex[i]->n = i;            // Заполняем массив вершин

vertex[i]->next = NULL;

}

arr = new int * [N];         // Массив для хранения кратчайших путей между вершинами

for (i = 0; i < N; ++i)

{

arr[i] = new int [N];

memset(arr[i], 0, N * sizeof(int));

}

Form1->Image1->Canvas->Pen->Color = RGB(200, 0, 0);

solin();

Form1->Image1->Canvas->Pen->Color = RGB(0, 0, 200);

}

}

Экранные формы: