Алгоритм Соллина построения дерева минимального веса

Задание:

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

для  графа: вершины графа – поля шахматной доски, поля соединяются ходом шахматного коня. Для каждого хода определен вес.

Граф задается массивом ребер.

Теория:

Алгоритм Соллина построения дерева минимального веса.

            Шаг 0. Соединить каждую вершину с ее ближайшим соседом (получим лес).

            Шаг 1. Удалить ребра, соединяющие вершины из одной компоненты связности полученного леса. Рассмотреть каждую из этих компонент как отдельную вершину. Перейти к шагу 0.

Вес каждого ребра будем определять как сумму приращений по х и по у, сложенную с 4 (чтобы не было отрицательного веса, т.к. в наихудшем случае сумма приращений может быть рана -3).

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

#include <iostream.h>

#include <stdlib.h>

#include <conio.h>

#include <stdio.h>

#include <math.h>

#include <graphics.h>

int edge[16][2]=   //массив ребер

{   {0,1},

{0,3},

{0,2},

{1,0},

{1,4},

{1,5},

{2,0},

{2,4},

{3,0},

{3,5},

{4,1},

{4,2},

{5,1},

{5,3},

{5,6},

{6,5}

}    ;

int peak[7][2]=   //массив вершин (поля шахматной доски)

{

{4,1},

{2,2},

{3,3},

{5,3},

{1,4},

{3,4},

{2,6}

};

static int kol = 0; //глобальная переменная для количества вершин

int color=0; //переменная для цвета

int lng[8]; //массив весов

int ed2[8][2]; //массив ребер (неповторяющихся)

int ind=0; //индекс для массивов весов и ребер

char msg[80]; //переменная для вывода текстового сообщения

char ms[80]; //переменная для вывода текстового сообщения

struct Arrow;

struct Node //структура, задающее узел дерева

{

Arrow *first; //указатель на первый элемент поддерева

int x, y; //координаты вершины

Node *next; //указатель на следующий узел дерева

int color; //цвет вершины

int p; //for sumaring ves

} *start_node = NULL; //вначале узлов нет

struct Arrow //структура поддерева

{

Node *end; //указатель на последний узел

double lengh; //веса ребер (длинна между точками)

int color;

Arrow *next; //указатель на следующий элемент

};

int fnd(int z,int v, int k) //вспомогательная функция, ищущая одинаковые ребра

{

for(int i=0;i<16;i++)

{

if(edge[i][0]==z && edge[i][1]==v && k<=i) return 1;

}

return 0;

}

void add_node (int i) //добавление узла

{

Node *tmp; //временная структура

Node *p = new (Node); //создаем структуру дерева

p->first = NULL; //начальное поддерево

p->x = peak[i][0]; //заполняем координаты

p->y = peak[i][1];

p->p=0;

p->next = NULL;

p->color = 0; //вершина не раскрашена

if (start_node == NULL) //если не было создано еще ни одной структуры

start_node = p; //сохраняем указатель на вновь созданную структуру

else //в противном случае

{

tmp = start_node;

while (tmp->next) //перемещаемся к последнему узлу

tmp = tmp->next;

tmp->next = p; //и добавляем вновь созданный узел

}

}

void add_arrow (int start, int end, int j)  //добавление поддерева

{

Arrow *p = new (Arrow);

Node *st = start_node, *ed = start_node;

Arrow *tmp;

int x, y;

for (x = 0; x < start; x++)

st = st->next; //находим узел, из которого выходит связь

for (y = 0; y < end; y++)

ed = ed->next; //находим узел в который входит связь

p->next = NULL;

p->end = ed;

int dx=peak[end][0]-peak[start][0]; //вычисляем приращения по х и по у для того, чтобы определить

//вес

int dy=peak[end][1]-peak[start][1];

if(fnd(end,start,j))

{lng[ind]=4+dx+dy; ed2[ind][0]=start; ed2[ind][1]=end; ind++;}

p->lengh = 4+dx+dy;

p->color=0;

if (st->first == NULL) //если дерево создается в первый раз

st->first = p;   //заполняем указатель на первое поддерево

else               //если уже есть поддеревья

{

tmp = st->first;

while (tmp->next)

tmp = tmp->next;

tmp->next=p; //заполняем указатель на следующее поддерево

}

}

void print (void) //вывод на экран

{

cleardevice ();

Node *tmp=start_node;