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

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

Войти
Регистрация
Восстановить пароль
 
acmilanfan1993
Сообщений: n/a
#1

Переделать программу с классами(Реализовать и исследовать алгоритм Краскала для нахождения стягивающего дерева) - C++

24.12.2012, 06:46. Просмотров 695. Ответов 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
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
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
 
typedef int* tint; // указатель на int
int main ()
{
int max; // Максимальный вес ребра
int n; // количество вершин
tint* G; // исходный граф
tint* H; // матрица списка ребер с весом
tint* K; //матрица, отмечающая принадлежность вершины компоненте
tint* T; // матрица остовного дерева
tint* L; // список ребер с ценами минимального дерева
//ввод графа
printf("Maximalno dopustimoe zna4enie vesa rebra = ");
scanf("%d", &max);
printf("Vvedite 4ilo vershin:  ");
scanf("%d", &n);
G = new tint [n];
for (int i=0; i<n; i++)
    G[i] = new int [n];
printf("\nVvedite nignij treugolnik matrici stoimosti:\n");
for (int i=1; i<n; i++)
    for (int j=0; j<i; j++)
    {
        scanf("%d", &G[i][j]);
    }
for (int i=1; i<n; i++)
    for (int j=0; j<i; j++)
        G[j][i] = G[i][j];
//выделение памяти для списка ребер
int n_edge=0;
for (int i=1; i<n; i++)
    for (int j=0; j<i; j++)
        if (G[i][j] < max && G[i][j] != 0)
            n_edge++;
H = new tint [n_edge];
for (int i=0; i<n_edge; i++)
    H[i] = new int [3];
 
int a=0;
for (int i=1; i<n; i++)
    for (int j=0; j<i; j++)
        if (G[i][j] < max && G[i][j] != 0)
        {
            H[a][0] = i+1;
            H[a][1] = j+1;
            H[a][2] = G[i][j];
            a++;
        }
printf("\n");
//сортировка ребер по возрастанию веса
int f,d,s;
for (int i=0; i<n_edge-1; i++)
    for (int j=0; j<n_edge-1; j++)
        if(H[j][2] > H[j+1][2])
        {
            f = H[j][2];
            H[j][2] = H[j+1][2];
            H[j+1][2] = f;
            d = H[j][0];
            H[j][0] = H[j+1][0];
            H[j+1][0] = d;
            s = H[j][1];
            H[j][1] = H[j+1][1];
            H[j+1][1] = s;
        }
//вывод ребер отсортированных по возрастанию веса
puts("Ves reber po vozrastaniyu:");
for (int i=0; i<n_edge; i++)
{
    printf("%d -->", H[i][0]);
    printf("%d = ", H[i][1]);
    printf("%d \n", H[i][2]);
}
for (int i=0; i<n_edge; i++)
{
    H[i][0]--;
    H[i][1]--;
}
//матрица для определения компоненты
K = new tint [n];
for (int i=0; i<n; i++)
    K[i] = new int [2];
for (int i=0; i<n; i++)
{
    K[i][0] = i;
    K[i][1] = 0;
}
//матрица остовного дерева
T = new tint [n];
for (int i=0; i<n; i++)
    T[i] = new int [n];
for (int i=0; i<n; i++)
    for (int j=0; j<n; j++)
        T[i][j] = 0;
//присоединение первого ребра
T[H[0][0]][H[0][1]] = H[0][2];
T[H[0][1]][H[0][0]] = H[0][2];
K[H[0][0]][1] = 1;
K[H[0][1]][1] = 1;
//алгорит соединения ребер без создания цикла:
int m=2; //номер компоненты
for (int i=1; i<n_edge; i++) //пройти по всем ребрам
if(K[H[i][0]][1] != K[H[i][1]][1])
//если 2 вершины не из одной компоненты
{
    if(K[H[i][0]][1] > 0 && K[H[i][1]][1] > 0)
//если обе вершины принадлежат разной компоненте
    {
        for(int j=0; j<n; j++)
            if(K[H[i][1]][1] == K[j][1])
                K[j][1] = K[H[i][0]][1];
        K[H[i][1]][1] = K[H[i][0]][1];
        T[H[i][0]][H[i][1]] = H[i][2];
        T[H[i][1]][H[i][0]] = H[i][2];
    }
    if((K[H[i][0]][1] > 0 && K[H[i][1]][1] == 0) || (K[H[i][0]][1] == 0 && K[H[i][1]][1] > 0))
//если одна вершина имеет компоненту а др. нет
    {
        if(K[H[i][0]][1] != 0)
            K[H[i][1]][1] = K[H[i][0]][1];
        if(K[H[i][1]][1] != 0)
            K[H[i][0]][1] = K[H[i][1]][1];
        T[H[i][0]][H[i][1]] = H[i][2];
        T[H[i][1]][H[i][0]] = H[i][2];
    }
    if(K[H[i][0]][1] == 0 && K[H[i][1]][1] == 0)
//если обе вершины не имели компоненты
    {
        K[H[i][0]][1] = m;
        K[H[i][1]][1] = m;
        T[H[i][0]][H[i][1]] = H[i][2];
        T[H[i][1]][H[i][0]] = H[i][2];
        m++;
    }
 
}//конец проверки всех ребер
//выделение памяти для списка ребер
n_edge=0;
for (int i=1; i<n; i++)
    for (int j=0; j<i; j++)
        if (T[i][j] < max && T[i][j] != 0)
            n_edge++;
        L = new tint [n_edge];
for (int i=0; i<n_edge; i++)
    L [i] = new int [3];
 
//вывод ребер
puts("Vivod reber minimalnogo vesa:");
a=0;
for (int i=1; i<n; i++)
    for (int j=0; j<i; j++)
        if(T[i][j] < max && T[i][j] != 0)
        {
            L[a][0] = i+1;
            L[a][1] = j+1;
            L[a][2] = T[i][j];
            a++;
        }
for (int i=0; i<n_edge; i++)
{
    printf("%d -->", L[i][0]);
    printf("%d = ", L[i][1]);
    printf("%d \n", L[i][2]);
}
int b=0;
for (int i=0; i<n_edge; i++)
    b+=L[i][2];
    // вывод стоимости
    printf("\n Stoimost dereva = %d", b);
getch ();
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.12.2012, 06:46
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Переделать программу с классами(Реализовать и исследовать алгоритм Краскала для нахождения стягивающего дерева) (C++):

Написать (переделать) программу с использованием ссылок в качестве параметров функций для нахождения минимального элемента из 3-х заданных - C++
Просто нахождение написал. Подскажите как использовать ссылки (&amp;) в качестве параметров функций. #include &quot;stdafx.h&quot; #include...

Помогите алгоритм для 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++
В общем задание такое, нужно переделать эту программу, я не знаю как это сделать, помогите люди добрые)) #include &lt;iostream&gt; ...

Алгоритм Краскала без векторов - C++
Помогите реализовать алгоритм Краскала без векторов на С++, могу заплатить.

Построение дерева отрезков для нахождения суммы на заданном интервале - C++
Здравствуйте! Ни у кого, случайно, нет несложного кода для подсчета суммы на интервале с помощью дерева отрезков? Очень нужно...

Нахождения минимального остовного дерева. Алгоритм Краскала - C#
как можно после того как прога подсчитает результат, рисовался бы граф чтоб Входные данные для программы (графы) читались из файла. и...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
24.12.2012, 06:46
Привет! Вот еще темы с ответами:

Реализовать алгоритм Краскала - Lisp
Добрый день, друзьяшки. Помогите пожалуйста, кому не будет трудным :) Препод дал такое задание: Сделал это задание на C++, но...

Поиск минимального остовного дерева в несвязном графе. Алгоритм Прима-Краскала - C#
Господа. Дело такое - нахожу я минимальное остовное дерево в связном графе (в котором каждая вершина с любой другой). А вот для несвязного...

Требуется реализовать алгоритм нахождения маршрута для пассажира на общественном транспорте - Lisp
Помогите, пожалуйста. Необходимо реализовать алгоритм решения задачи о нахождении маршрута для пассажира на общественном...

Исследовать алгоритм нахождения Эйлерова пути в неориентированном графе - C (СИ)
Задание: Реализовать в виде программы и исследовать алгоритм нахождения эйлерова пути в неориентированном графе. и еще тупой вопрос...


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

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

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