Форум программистов, компьютерный форум CyberForum.ru

Поиск остовного леса методом Соллина - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Итерационные и рекурсивные алгоритмы http://www.cyberforum.ru/cpp-beginners/thread854644.html
Вычислить на ЭВМ значение суммы членов бесконечного ряда с заданной точностью и значение суммы, определяемое пределом суммы ряда ( по формуле). Напечатать значения сумм и число циклов ряда, вошедших в сумму. На с++. Sin(x)=∑(-1)n-1*x^(2n-1)/(2n-1)!=x - x^3/3! + x^5/5!-x^7/7! +x^9/9! - x^11/11!
C++ Чистая виртуальная функция Скажите, может ли чистая виртуальная функция иметь тело? В книге написано что может, но не написано как. Пытался сам определить по-разному - не получилось. В интернете нашел пару примеров с телами, но они тоже не работают. http://www.cyberforum.ru/cpp-beginners/thread854601.html
Надо написать функцию, которая по массиву действительных чисел x1, x2, ..., xn находит произведение положительных элементов массива C++
Надо написать функцию, которая по массиву действительных чисел x1, x2, ..., xn находит произведение положительных элементов массива.Вот у меня уже есть программа, только здесь для 10 элементов. Как сделать для n- количества? #include <iostream> using namespace std; float plusDmg(float a, int n) { int i = 0; float dmg = 1; while (i < n) { if (a > 0)
vector.clear C++
У меня вопрос по поводу метода clear(). Пусть у меня в векторе было 30 элементов, после вызова этого метода их стало 0, поэтому size() тоже вернет 0. Но вот capacity() показывает 30, т.е. если я правильно понимаю, в оперативке под эту переменную все ещё выделено 30 * sizeof(int) байт памяти => если массив очень большой, то он продолжает занимать довольно много места, так? Как его тогда удалить из...
C++ точность, настраиваемая вручную http://www.cyberforum.ru/cpp-beginners/thread854568.html
Мне нужно произвести расчет с точность 27 знаков после запятой. Long double не хватает. Как определить вручную? Добавлено через 2 часа 4 минуты :umnik:
C++ FreeConsole не работает FreeConsole не работает если программу запустить через другую программу командой system("start путь к программе"); а если саму программу без посторонних включить то работает, что делать подробнее

Показать сообщение отдельно
Vaste
1 / 1 / 0
Регистрация: 23.04.2012
Сообщений: 42
03.05.2013, 08:25     Поиск остовного леса методом Соллина
Доброго времени суток. Передо мной встала задача найти остовной лес минимальной стоимости методом Соллина. Интернет предложил единственный вариант реализации данного алгоритма (приведён ниже). Сразу скажу, ошибка в том, что он не делает разницы было ли рассмотрено ребро или нет (т.е. 2 раза рассмотреть одно и то же ребро, от начальной вершины к конечной и наоборот). Соответственно, к результирующей стоимости леса дважды добавляет одно и то же ребро. Кто в курсе как исправить - буду рад идеям.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
/*
Поиск остовного леса минимального веса методом Соллина
(длины ребер - расстояния между точками) вершины графа - точки плоскости.
Алгоритм Соллина построения дерева минимального веса.
1. Соединить каждую вершину с ее ближайшим соседом.
2. Удалить ребра, соединяющие вершины из одной компоненты связности полученного леса.
Рассмотреть каждую из этих компонент как отдельную вершину. Перейти к 1.
*/
#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
 
#define KT 6    //число точек
 
int koord[KT][2] ={{5,5},{5,7},{8,6},{2,6},{3,3},{7,3}};    //координаты точек
 
int edges[14][2]={ //массив рёбер в формате "начальная вершина - конечная вершина"
       {0,1},
       {0,3},
 
       {1,0},
       {1,3},
 
       {2,4},
       {2,5},
 
       {3,0},
       {3,1},
       {3,4},
 
       {4,2},
       {4,3},
       {4,5},
 
       {5,2},
       {5,4}};
int kol = 0; //порядковый номер вершин графа
float resultweigth = 0;
struct Arrow;
//Структура вершин графа
struct Vertex
{
    Arrow *first; //если из вершины выходит связь
    int x, y;         //точки
    int number;     //номер точки
    Vertex *next;       //следующая вершина
} *start_Vertex = NULL;
//Структура ребра
struct Arrow
{
    Vertex *end;        //вершина, с которой связь
    double lengh;     //вес
    Arrow *next;      //если есть еще связи
};
//Создаем вершины
void add_Vertex (int i)
{
    Vertex *p = new (Vertex);
    p->first = NULL;
    p->next = NULL;
    p->x = koord[i][0];
    p->y = koord[i][1];
    p->number = kol++; //порядковый номер добавляемой вершины
    if (start_Vertex == NULL) //если добавляется первая вершина
       start_Vertex = p;
    else //если не первая
    {
        Vertex *tmp=NULL;
        tmp = start_Vertex;
        while (tmp->next) //доходим до последней вершины
              tmp = tmp->next;
        tmp->next = p; //присваиваем её указателю на следующую вершину
    }                  //адрес новосозданной вершины
}
//Связываем вершины
void add_arrow (int start, int end)
{
    int x, y;//переменные под (x-x0) и (y-y0)
    Arrow *p = new (Arrow);
    Vertex *st = start_Vertex, *ed = start_Vertex;
 
    for (x = 0; x < start; x++)
        st = st->next;          //находим узел, из кот-го выходит ребро
    for (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                    //симметрична
    {
      Arrow *tmp;
      tmp = st->first;
      while (tmp->next)
        tmp = tmp->next;
      tmp->next=p;
    }
}
 
void sollin(void)
{   //алгоритм Соллина
 double min=100;//эталонный вес ребра
 int startnumber,endnumber;//индексы начала и конца вершин
 Vertex *startvertex,*endvertex;
 Arrow *edge;
 startvertex=start_Vertex;
 endvertex=start_Vertex;
  //идем по вершинам
    while(startvertex)
  {
        edge=startvertex->first; min=100;
    //идём по рёбрам
    while(edge)
    {
      if(edge->lengh<min)
        {   //поиск минимального ребра
          min=edge->lengh;
          endvertex=edge->end;
                }
            startnumber=startvertex->number;
            endnumber=endvertex->number;
            edge=edge->next;
    }
        printf("\nStart: %d ",startnumber);
        printf("End: %d",endnumber);
        printf("\tMin weigth = %f",min);
    resultweigth+=min;
      startvertex=startvertex->next;
    }
} 
void print(void)
{       //вывод вершин и связей
    Vertex *tmp = start_Vertex;
    Arrow *ar = NULL;
    while (tmp)
    { //идём по вершинам
      printf ("%d vertex is connected with: \n", tmp->number);
      if (!(tmp->first))
        printf ("No connection");
      else
      {
        ar = tmp->first;
        while (ar)
        {
          printf ("\t%d (Weigth: %4.3f)\n", ar->end->number, ar->lengh);
          ar = ar->next;
        }
      }
      tmp = tmp->next;
    }
} 
 
void main()
{
  int i, j, k=0;
  system("cls");
  for (i = 0; i < KT; i++)
    add_Vertex (i);
  for (i = 0; i < KT; i++)
    for (j = 0; j < KT; j++)
      for(k = 0; k < 14; k++)
        if ((i == edges[k][0]) && (j == edges[k][1]))
          add_arrow (i, j);
  print(); //распечатка вершин и рёбер
  printf("\nAfter Sollin-ing\n");
  sollin(); //поиск остовного дерева
  printf("\n Total weigth = %.3f",resultweigth);
  getch();
}
Для администрации: не нашёл подобную тему, вот и создал новую. Если будет необходимо - перенесите куда надо, буду благодарен.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 18:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru