Поиск остовного леса минимального веса методом Соллина (длины ребер - расстояния между точками) вершины графа - точки плоскости на C++


Добавил:DMT
Дата создания:25 апреля 2008, 16:13
Дата обновления:25 апреля 2008, 16:13
Просмотров:5865 последний позавчера, 0:43
Комментариев: 0
Поиск остовного леса минимального веса методом Соллина (длины ребер - расстояния между точками) вершины графа - точки плоскости
Алгоритм Соллина построения дерева минимального веса.
1. Соединить каждую вершину с ее ближайшим соседом.
2. Удалить ребра, соединяющие вершины из одной компоненты связности полученного леса. Рассмотреть каждую из этих компонент как отдельную вершину. Перейти к 1.
Код на C++
  1. #include <stdlib.h>
  2. #include <conio.h>
  3. #include <stdio.h>
  4. #include <math.h>
  5.  
  6. #define KT 5	//число точек
  7.  
  8. int koord[KT][2] ={{4, 10},{8, 9},{14,9},{10,7},{6, 5}};	//координаты точек
  9.  
  10. int matr[KT][KT] ={	//матрица смежности
  11.     	{0,1,1,1,1},
  12. 	{1,0,1,1,0},
  13. 	{1,1,0,0,1},
  14. 	{1,1,0,0,1},
  15. 	{1,0,1,1,0}
  16. };
  17.  
  18. static int kol = 0;
  19.  
  20. struct Arrow;
  21. struct Node{		//вершины графа
  22.     Arrow *first;   	//если из вершины выходит связь  
  23.     int x, y;		//точки
  24.     int kol_vo;		//номер точки
  25.     Node *next;		//следующая вершина
  26. } *start_node = NULL;
  27.  
  28. struct Arrow{		//ребра
  29.     Node *end;		//вершина, с которой связь
  30.     double lengh;	//вес
  31.     Arrow *next;	//если  есть еще связи
  32. };
  33.  
  34. void add_node (int i){	//создаем вершины
  35.     Node *tmp=NULL;
  36.     Node *p = new (Node);
  37.  
  38.     p->first = NULL;
  39.     p->x = koord[i][0];
  40.     p->y = koord[i][1];
  41.     p->kol_vo = kol++;
  42.     p->next = NULL;
  43.  
  44.     if (start_node == NULL)
  45.        start_node = p;
  46.     else{
  47.         tmp = start_node;
  48.         while (tmp->next)
  49.               tmp = tmp->next;
  50.         tmp->next = p;
  51.     }
  52. }
  53.  
  54.  
  55. void add_arrow (int start, int end){	//связываем вершины
  56.     Arrow *p = new (Arrow);
  57.     Node *st = start_node, *ed = start_node;
  58.     Arrow *tmp;
  59.     for (int x = 0; x < start; x++)
  60.         st = st->next; 			//находим узел, из кот-го выходит связь
  61.     for (int y = 0; y < end; y++)
  62.         ed = ed->next; 			//находим узел в кот-ю входит связь
  63.  
  64.     x = ed->x - st->x; //координата х вектора
  65.     y = ed->y - st->y; //координата y вектора
  66.  
  67.     p->next = NULL;
  68.     p->end = ed;
  69.     p->lengh = sqrt(x * x + y * y);	//длина между точками
  70.  
  71.     if (st->first == NULL)
  72.        st->first = p;   		//добавлять для ed не надо, т.к. матрица
  73.     else  {                              //симметрична
  74.         tmp = st->first;
  75.         while (tmp->next)
  76.               tmp = tmp->next;
  77.         tmp->next=p;
  78.     }
  79. }
  80.  
  81. void collin(void){	//алгоритм Соллина
  82.  double min=100;
  83.  int nv,kv;
  84.  Node *tv,*tn;
  85.  Arrow *l;
  86. tv=start_node;
  87. tn=start_node;
  88. 	while(tv){					//идем по вершинам
  89. 		l=tv->first; min=100;
  90. 			while(l){			//по связям
  91. 				if(l->lengh<min){	//проверка на мин.
  92. 					min=l->lengh;
  93. 					tn=l->end;
  94. 				}
  95. 			nv=tv->kol_vo;
  96. 			kv=tn->kol_vo;
  97. 			l=l->next;
  98. 			}
  99. 		printf("\nStart= %d",nv);
  100. 		printf("\tEnd= %d",kv);
  101. 		printf("\nMin vec= %f",min);
  102. 	tv=tv->next;
  103. 	}
  104. } 
  105. void print(void){		//вывод 
  106.     Node *tmp = start_node;
  107.     Arrow *ar=NULL;
  108.     while (tmp){
  109.         printf ("%d tochka cvyazana c tochkami: \n", tmp->kol_vo);
  110.         if (!(tmp->first))
  111.            printf ("net cvyaze'");
  112.         else{
  113.             ar = tmp->first;
  114.             while (ar){
  115.                 printf ("\t%d (Dlina: %7.3f)\n", ar->end->kol_vo, ar->lengh);
  116.                 ar = ar->next;
  117.             }
  118.         }
  119.         tmp = tmp->next;
  120.     }
  121. } 
  122.  
  123. void main()
  124. {
  125.     clrscr();
  126.     for (int i = 0; i < KT; i++)
  127.         add_node (i);
  128.     for ( i = 0; i < KT; i++)
  129.         for (int j = 0; j < KT; j++)
  130.             if (matr[i][j] != 0)
  131.                add_arrow (i, j);
  132. print();
  133. printf("\nPosle sortirovki Collina");
  134. collin();
  135. }
При использовании обязательна ссылка на http://DMTSoft.ru
up