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


Добавил:DMT
Дата создания:25 апреля 2008, 16:13
Дата обновления:25 апреля 2008, 16:13
Просмотров:5918 последний позавчера, 9:58
Комментариев: 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