Поиск остовного леса минимального веса методом Соллина (длины ребер - расстояния между точками) вершины графа - точки плоскости
Алгоритм Соллина построения дерева минимального веса.
1. Соединить каждую вершину с ее ближайшим соседом.
2. Удалить ребра, соединяющие вершины из одной компоненты связности полученного леса. Рассмотреть каждую из этих компонент как отдельную вершину. Перейти к 1.
Код на C++ #include <stdlib.h> #include <conio.h> #include <stdio.h> #include <math.h> #define KT 5 //число точек int koord[KT][2] ={{4, 10},{8, 9},{14,9},{10,7},{6, 5}}; //координаты точек int matr[KT][KT] ={ //матрица смежности {0,1,1,1,1}, {1,0,1,1,0}, {1,1,0,0,1}, {1,1,0,0,1}, {1,0,1,1,0} }; static int kol = 0; struct Arrow; struct Node{ //вершины графа Arrow *first; //если из вершины выходит связь int x, y; //точки int kol_vo; //номер точки Node *next; //следующая вершина } *start_node = NULL; struct Arrow{ //ребра Node *end; //вершина, с которой связь double lengh; //вес Arrow *next; //если есть еще связи }; void add_node (int i){ //создаем вершины Node *tmp=NULL; Node *p = new (Node); p->first = NULL; p->x = koord[i][0]; p->y = koord[i][1]; p->kol_vo = kol++; p->next = NULL; 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){ //связываем вершины Arrow *p = new (Arrow); Node *st = start_node, *ed = start_node; Arrow *tmp; for (int x = 0; x < start; x++) st = st->next; //находим узел, из кот-го выходит связь for (int y = 0; y < end; y++) ed = ed->next; //находим узел в кот-ю входит связь x = ed->x - st->x; //координата х вектора y = ed->y - st->y; //координата y вектора p->next = NULL; p->end = ed; p->lengh = sqrt(x * x + y * y); //длина между точками if (st->first == NULL) st->first = p; //добавлять для ed не надо, т.к. матрица else { //симметрична tmp = st->first; while (tmp->next) tmp = tmp->next; tmp->next=p; } } void collin(void){ //алгоритм Соллина double min=100; int nv,kv; Node *tv,*tn; Arrow *l; tv=start_node; tn=start_node; while(tv){ //идем по вершинам l=tv->first; min=100; while(l){ //по связям if(l->lengh<min){ //проверка на мин. min=l->lengh; tn=l->end; } nv=tv->kol_vo; kv=tn->kol_vo; l=l->next; } printf("\nStart= %d",nv); printf("\tEnd= %d",kv); printf("\nMin vec= %f",min); tv=tv->next; } } void print(void){ //вывод Node *tmp = start_node; Arrow *ar=NULL; while (tmp){ printf ("%d tochka cvyazana c tochkami: \n", tmp->kol_vo); if (!(tmp->first)) printf ("net cvyaze'"); else{ ar = tmp->first; while (ar){ printf ("\t%d (Dlina: %7.3f)\n", ar->end->kol_vo, ar->lengh); ar = ar->next; } } tmp = tmp->next; } } void main() { clrscr(); for (int i = 0; i < KT; i++) add_node (i); for ( i = 0; i < KT; i++) for (int j = 0; j < KT; j++) if (matr[i][j] != 0) add_arrow (i, j); print(); printf("\nPosle sortirovki Collina"); collin(); }
|