Реализовать Алгоритм Краскала

@KaraSandberg · Регистрация: 15.10.2019

Студворк — интернет-сервис помощи студентам

Нужно исправить код. Ошибки.

Какой код лучше подойдёт?

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
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
 
vector< vector<int> > ady;
vector< vector<int> > Grafo :: kruskal(){
    vector< vector<int> > adyacencia = this->ady;
    vector< vector<int> > arbol(cn);
    vector<int> pertenece(cn);
 
    for(int i = 0; i < cn; i++){
        arbol[i] = vector<int> (cn, INF);
        pertenece[i] = i;
    }
 
    int nodoA;
    int cn; //число вершин
    int nodoB;
    int arcos = 1;
    while(arcos < cn){
        int min = INF;
        for(int i = 0; i < cn; i++)
            for(int j = 0; j < cn; j++)
                if(min > adyacencia[i][j] && pertenece[i] != pertenece[j] && adyacencia[i][j] != 0){
                    min = adyacencia[i][j];
                    nodoA = i;
                    nodoB = j;
                }
        if(pertenece[nodoA] != pertenece[nodoB]){
            arbol[nodoA][nodoB] = min;
            arbol[nodoB][nodoA] = min;
 
         int temp = pertenece[nodoB];
         pertenece[nodoB] = pertenece[nodoA];
         for(int k = 0; k < cn; k++)
          if(pertenece[k] == temp)
           pertenece[k] = pertenece[nodoA];
 
            arcos++;
        }
    }
    return arbol;
    system ("pause");
}

Добавлено через 7 минут
Wдерева = ∑ wy = 1+1+2+5 = 9
Реализовать – это все:
Граф связный
Числа от 1 до 10, Матрица 10×10, число вершин = 10
Могут повторяться
Wy(Random) {█(i=1,n-1@j=2,n)┤
W*; = Wy – присваиваем.
Wi,i = 0 – заполняем 0.

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
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
 
 
/*
Объявляем структуру Ребро, которой будем пользоваться для построения графа и дерева
*/
struct edge{
    int x, y; //вершины
    edge(){}
    edge(int a, int b){
        x = a;
        y = b;
    }
};
 
int main() {
    int n, m;
    cin >> n >> m;
 
    vector <edge> graph (m); //ребра исходного графа
    vector <edge> tree; //ребра дерева
    vector <int> variety (n); //множество вершин
 
    /*
    variety[n] = m - вершина n принадлежит множеству m.
    Следующий цикл определяет для каждой вершины свое множество
    */
    for (int i = 0; i < n; i++){
        variety[i] = i;
    }
 
    /*
    Заполняем ребра исходного графа значениями из стандартного ввода
    */
    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        graph[i].x = a;
        graph[i].y = b;
    }
 
    /*
    Проверяем вершины каждого ребра.
    Если вершины не принадлежат одному и тому же множеству,
    но такое ребро добавляем в наше дерево, а вершины помещаем в одно множество
    */
    for (int i = 0; i < m; i++){
        int a = graph[i].x;
        int b = graph[i].y;
        if (variety[a] != variety[b]){
            tree.push_back(graph[i]);
            int old_variety = variety[b], new_variety = variety[a];
            for (int j = 0; j < n; j++){
                if (variety[j] == old_variety){
                    variety[j] = new_variety;
                }
            }
 
 
 
        }
    }
 
 
    for(int i = 0; i < n - 1; i++){ //по принципу построения дерева, оно содержит n-1 ребро
        cout << tree[i].x << " " << tree[i].y;
        if (i != n-2){
            cout << endl;
        }
    }
    return 0;
}

Добавлено через 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);
}

Добавлено через 3 минуты

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
#include <iostream>
#include <vector>
#include <math.h>
#include <conio.h>
#include <list>
using namespace std;
 
 
int m;
vector < pair < int, pair<int,int> > > g (m); // вес - вершина 1 - вершина 2
 
int cost = 0;
vector < pair<int,int> > res;
 
sort (g.begin(), g.end());
vector<int> tree_id (n);
for (int i=0; i<n; ++i)
    tree_id[i] = i;
for (int i=0; i<m; ++i)
{
    int a = g[i].second.first,  b = g[i].second.second,  l = g[i].first;
    if (tree_id[a] != tree_id[b])
    {
        cost += l;
        res.push_back (make_pair (a, b));
        int old_id = tree_id[b],  new_id = tree_id[a];
        for (int j=0; j<n; ++j)
            if (tree_id[j] == old_id)
                tree_id[j] = new_id;
    }
    return 0;
}

Добавлено через 31 минуту

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
vector<int> p (n);
 
int dsu_get (int v) {
    return (v == p[v]) ? v : (p[v] = dsu_get (p[v]));
}
 
void dsu_unite (int a, int b) {
    a = dsu_get (a);
    b = dsu_get (b);
    if (rand() & 1)
        swap (a, b);
    if (a != b)
        p[a] = b;
}
 
int m;
vector < pair < int, pair<int,int> > > g;
 
int cost = 0;
vector < pair<int,int> > res;
 
sort (g.begin(), g.end());
p.resize (n);
for (int i=0; i<n; ++i)
    p[i] = i;
for (int i=0; i<m; ++i) {
    int a = g[i].second.first, b = g[i].second.second, l = g[i].first;
    if (dsu_get(a) != dsu_get(b)) {
        cost += l;
        res.push_back (g[i].second);
        dsu_unite (a, b);
    }
}

@Like_society · 19.11.2019, 21:11

Мне тоже интересно, какой здесь вариант актуальный и правильный? Нужно помочь и исправить.

@KaraSandberg · 23.11.2019, 20:24 **[ТС]**

Поднять тему

@KaraSandberg · 15.12.2019, 16:17 **[ТС]**

UP!

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@Like_society -12 / 6 / 4 Регистрация: 19.01.2017 Сообщений: 584
	19.11.2019, 21:11
	Мне тоже интересно, какой здесь вариант актуальный и правильный? Нужно помочь и исправить. 1

@KaraSandberg 11 / 9 / 2 Регистрация: 15.10.2019 Сообщений: 161
	23.11.2019, 20:24 [ТС]
	Поднять тему 0

@KaraSandberg 11 / 9 / 2 Регистрация: 15.10.2019 Сообщений: 161
	15.12.2019, 16:17 [ТС]
	UP! 0