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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.67
Sakura Soul
16 / 2 / 1
Регистрация: 12.12.2011
Сообщений: 37
#1

Алгоритм Крускала - C++

05.11.2012, 20:24. Просмотров 3251. Ответов 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
177
178
179
#include <iostream>
#include <conio.h>
 
using namespace std;
/************************************************/
/*Создаем класс граф                           */
/***********************************************/
class Graf
{
    private :
    int MaxNodes;//Максимальное кол-во узлов
    int *nodes;//массив узлов для раскраски
    int num_vershina;//кол-во вершин
    int num_rebro;//кол-во ребер
    int Last_vershina;//цвет последней окрашеной вершины
    /*структура узла*/
    struct uzel
    {
        int v1;
        int v2;
        int wes;
    }*uzels;
    public :
    Graf();
    void InitGraf();//функция задающая граф
     void sort();//сортировка ребер по возрастанию
     int GetColor(int n);//получает цвет ребра,n - номер вершины
     void OutTree();//вывод дерева на экран
 
};
/*******************************************/
/*конструктор                              */
/*******************************************/
 Graf::Graf()
 {
     MaxNodes = 50;
     nodes = new int[MaxNodes];
     uzels = new uzel[MaxNodes];
 }
 /****************************************/
 /*Функция задающая граф                 */
 /****************************************/
void Graf::InitGraf()
 {
     setlocale(LC_ALL,"Russian");
     cout<<"Ввидите число вершин"<<endl;
      cin>>num_vershina;
      cout<<endl
          <<"Введите число ребер"<<endl;
          cin>>num_rebro;
 
       // Задаем начальные цвета вершинам
       for(int i = 0 ;i<num_vershina;i++)
        nodes[i] = -1-i;
        cout<<endl
            <<"Колличество ребер :"<<num_rebro<<endl
            <<"Введите их в формате : вершина 1,вершина 2,вес"
            <<endl;
            for(int i = 0;i < num_rebro;i++)
            {
              cout<<endl<<"Вершина 1 = ";cin>>uzels[i].v1;
               cout<<"Вершина 2 = ";cin>>uzels[i].v2;
                cout<<"Вес = ";cin>>uzels[i].wes;
            }
            cout<<endl<<"Граф задан"<<endl;
 }
 /******************************************************************************/
/* Фунция сортирующая ребра графа по весу начиная с наименьшего               */
/******************************************************************************/
 
void Graf::sort()
{
    uzel tmp;//обьект типа узел
    // Пузырьковая сортировка
 
    for(int i=0;i < num_rebro - 1;i++)
     for (int j = 0;j < num_rebro - 1;j++)
     if (uzels[j].wes > uzels[j+1].wes)
     {
         tmp = uzels[j];
         uzels[j] = uzels[j+1];
         uzels[j+1] = tmp;
     }
 
}
/******************************************************************************/
/* Функция, получающая цвет ребра                                             */
/* Параметры:                                                                 */
/* n - номер вершины                                                          */
/******************************************************************************/
int Graf::GetColor(int n)
{
 
   // Если цвет вершины с номером n - отрицательный, то...
   if(nodes[n]<0)
   {
       Last_vershina = n;//цвет последней окрашенной вершины
        return nodes[Last_vershina];//возвращаем его
   }
    else
    {
        int color;
        // Получаем цвет вершины с номером n
        color = GetColor(nodes[n]);
         nodes[n] = Last_vershina;// окрашиваем его в цвет вершины, с которой объединяем
         return color;// возвращаем цвет
    }
 
}
/******************************************************************************/
/* Функция, выводящая дерево на экран                                         */
/******************************************************************************/
 
void Graf::OutTree()
{
    sort();
    setlocale(LC_ALL,"Russian");
     // Сортируем ребра по возрастанию
 
     cout<<"Минимальное остовное дерево состоит из ребер с весами "<<endl;
     for(int i=0;i<num_rebro;i++)
     {
         int color1 = GetColor(uzels[i].v2);// получаем цвет второй вершины
         int color2 = GetColor(uzels[i].v1);  // получаем цвет первой вершины
    // Если ребро соединяет вершины различных цветов, то...
 
        if(color2 != color1)
        {
    // ...перекрашиваем вершины в цвет ребра
    nodes[Last_vershina] = uzels[i].v2;
// добавляем вершину в минимальное остовное дерево
     cout<<endl
         <<uzels[i].wes;
        }
     }
 
 
}
 
 
 
 
int main()
{
    setlocale(LC_ALL,"Russian");
     Graf graf;
        int c = 1;
 
        while(c != 3)
        {
 
                cout<<"Операции"<<endl;
                cout<<"1. Задать граф"<<endl;
                cout<<"2. Построить дерево"<<endl;
                cout<<"3. Выход"<<endl;
                cout<<">> "<<endl;
 
                cin>>c;
 
                switch (c)
                {
                        case 1:
                                graf.InitGraf();
                                break;
 
                        case 2:
                                graf.OutTree();
                                break;
 
                        case 3:
                                break;
 
                        default:
                                cout<<endl<<"Неверный выбор"<<endl;
                         break;
                }
        }
return(1);
}
0
Миниатюры
Алгоритм Крускала  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2012, 20:24
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Крускала (C++):

Алгоритм Крускала - C++
Задача:Порядок ввода:Порядок вывода:Пример ввода:Пример вывода:Органичения:я решил ее с помощью алгоритма Прима вот мое решение#include...

Алгоритм, обратный алгоритму Крускала - C++
Требуется реализовать алгоритм поиска максимального остовного дерева

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Помогите алгоритм для char переделать в алгоритм для float - C++
char* DecToBin(char x, char* str) { int i; for (i = sizeof(x)*8-1; i&gt;=0; i--) { str = (x&amp;1 == 1) ? '1' : '0'; x = x &gt;&gt;...

Волновой алгоритм (алгоритм Ли) - C++
Здравствуйте! У кого-нибудь есть реализованный волновой алгоритм (алгоритм Ли) ? Дело в том, что я игрушку захотел написать (что-то...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Sakura Soul
16 / 2 / 1
Регистрация: 12.12.2011
Сообщений: 37
05.11.2012, 20:26  [ТС] #2
я в классах еще не силен. Крускала метод знаю,а программно тоже затрудняюсь реализовать.
0
LoSyAsH
6 / 6 / 6
Регистрация: 22.10.2015
Сообщений: 74
Завершенные тесты: 2
03.12.2016, 14:51 #3
Вдруг кто-то ещё наткнётся на этот пост. вот реализация в лоб без классов. http://www.e-maxx-ru.1gb.ru/algo/mst_kruskal
Хотя не совсем, т.к. работает за N^2 что не есть хорошо.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.12.2016, 14:51
Привет! Вот еще темы с ответами:

Алгоритм Прима, Крускала - Delphi
Нашел код реализации алгоритмов, пробовал сделать форму но выдает кучу ошибок. program Project1; uses Forms, Unit1 in...

Алгоритм Крускала и Прима - Алгоритмы
Здраствуйте, алгоритм Крускала и Прима можна ли использовать для отрицательных значений ребер графа? Если нет, то почему?

Алгоритм Крускала (Краскала) на Assembler - Assembler
Добрый день! Кто-то имеет программную реализацию алгоритма Крускала (Краскала) на FASM???

Алгоритм Прима-Крускала - нужен пример - Delphi
Народ , подскажите пожалуйста , где можно найти принцип алгоритма прима - краскла . Вообще все интересует по этой теме , по этому если не...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru