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


Добавил:DMT
Дата создания:25 апреля 2008, 14:28
Дата обновления:25 апреля 2008, 14:28
Просмотров:5118 последний сегодня, 0:12
Комментариев: 0
Поиск остовного леса минимального веса методом обхода в глубину (длины ребер считаются равными 1)
Вершины графа - точки плоскости на C++
Код на C++
  1. #include <stdio.h>
  2.  
  3. #define N 9
  4.  
  5. struct Vert
  6. {
  7. int n;
  8. Vert *next;
  9. };
  10.  
  11. Vert *a[N];
  12. int was[N];
  13. int tree[N][N];
  14.  
  15. // initialization
  16. void init()
  17. {
  18. for (int i = 0; i < N; i++)
  19. {
  20. a[i] = new Vert;
  21. a[i]->n = i;
  22. a[i]->next = 0;
  23. }
  24. }
  25.  
  26. // add edge from v to what
  27. void add(int v, int what)
  28. {
  29. Vert *n = a[v];
  30. while (true)
  31. {
  32. if (n->n == what) return;
  33. if (!(n->next)) break;
  34. n = n->next;
  35. }
  36. Vert *newV = new Vert;
  37. newV->next = NULL;
  38. newV->n = what;
  39. n->next = newV;
  40. }
  41.  
  42. // delete edges
  43. void remove()
  44. {
  45. Vert *n, *cur;
  46. for (int i = 0; i < N; i++)
  47. {
  48. n = a[i];
  49. while (n)
  50. {
  51. cur = n;
  52. n = n->next;
  53. delete cur;
  54. }
  55. }
  56. }
  57.  
  58. // add edge from v1 to v2 and from v2 to v1
  59. void edge(int v1, int v2)
  60. {
  61. add(v1, v2);
  62. add(v2, v1);
  63. }
  64.  
  65. // deep search of spanning tree
  66. void gettree(int v)
  67. {
  68. tree[v][v] = 1;
  69. was[v] = 1;
  70. Vert *n;
  71. for (n = a[v]; n; n = n->next)
  72. if (!was[n->n])
  73. {
  74. tree[n->n][v] = tree[v][n->n] = 1;
  75. gettree(n->n);
  76. }
  77. }
  78.  
  79. // spanning forest
  80. void gettrees()
  81. {
  82. int i;
  83. for (i = 0; i < N; i++) was[i] = 0;
  84. for (i = 0; i < N; i++) if (!was[i]) gettree(i);
  85. }
  86.  
  87. // show matrix
  88. void show(int *m)
  89. {
  90. for (int i = 0; i < N; i++)
  91. {
  92. for (int j = 0; j < N; j++)
  93. printf("%d ", m[i * N + j]);
  94. printf("\n");
  95. }
  96. printf("---------------------\n");
  97. }
  98.  
  99. // show list
  100. void showlist(Vert **list)
  101. {
  102. Vert *n;
  103. for (int i = 0; i < N; i++)
  104. {
  105. n = a[i];
  106. while (n)
  107. {
  108. if (n->next)
  109. printf("%d -> ", n->n);
  110. else
  111. printf("%d", n->n);
  112. n = n->next;
  113. }
  114. printf("\n");
  115. }
  116. printf("---------------------\n");
  117. }
  118.  
  119. main()
  120. {
  121. for (int i = 0; i < N; i++)
  122. for (int j = 0; j < N; j++)
  123. tree[i][j] = 0;
  124. init();
  125. edge(0, 1);
  126. edge(0, 3);
  127. edge(0, 2);
  128. edge(1, 2);
  129. edge(2, 3);
  130. edge(4, 5);
  131. edge(4, 6);
  132. edge(5, 7);
  133. edge(6, 7);
  134. edge(6, 8);
  135. edge(7, 8);
  136. gettrees();
  137. showlist(a);
  138. show(&tree[0][0]);
  139. remove();
  140. }
При использовании обязательна ссылка на http://DMTSoft.ru
up