Поиск минимального остовного дерева на графе

@frEEze00 · Регистрация: 10.07.2014

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

Переделал программу найденную в интернете, написал через функцию.

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
#include <iostream>;
#include <fstream>;
 
 
using namespace std;
 
void creatFile(int maxCost, int kolVer, int **cost){
    //функция, создающая текстовый файл с заданным названием и записывающая в него данные для хранения
    int i,j;
    char name[50];
    cout<<"Введите название файла:";
    cin >> name;
    strcat(name, ".txt");
    ofstream out(name);
    out<<maxCost<<"\n"; //Записываем в первую строку файла максимальный вес ребра
    out<<kolVer<<"\n";  //Записываем во вторую строку количество вершин
 
    //в следующии строки записываем матрицу смежности
for (i=1; i<=kolVer; i++)
{   
    for (j=1; j<=kolVer; j++)
    {   
        out<<cost[i][j]<<" ";
    }
    out<<"\n";
}
 
    out.close();
    cout<<"Файл создан\n";
};
void poiskMinOstDer(int maxCost, int kolVer, int **cost)
{       //Функциия поиска минимального оставного дерева на графе
    int min=maxCost;
    int minCost=0;
    int i,i2,i3,j,j2,j3,n,shet=1,iRebra=0;
    bool used[99]={false};
    used[1]=true;
    int rebro[99]={0};
    
    while (shet<kolVer)
    {
        for (i=1; i<=kolVer; i++)
        {
            for (j=1; j<=kolVer; j++)
            {
                if (cost[i][j]<min) 
                {
                    if (used[i]!=false)
                    {
                        min=cost[i][j];
                        i2=i3=i;
                        j2=j3=j;
                    }
                        if (used[j3]==false || used[j3]==false)
                        {
                            rebro[iRebra]=j2;
                            iRebra++;
                            shet++;
                            minCost=minCost+min;
                            used[j2]=true;
                        }
                    cost[i2][j2]=cost[j2][i2]=maxCost;
                }
            }
        }
    }
    cout<<1<<" --> ";
    for (i=0; i<kolVer-1; i++)
    {
        cout<<rebro[iRebra];
        if (i<kolVer-2){cout<<" --> ";}
    }
    cout<<"\n Минимальная стоимость: "<<minCost;
};
int main(){
setlocale (LC_ALL, "RUS");
int i,j;
int maxCost=100; //Максимальный вес ребра
int kolVer; //Количество вершин графа
int **cost;
cost = new int *[40];
for (i=0; i<40; i++){cost[i]=new int[40];}
 
 
cout<<"Введите максимальный вес ребра:\n";
cin>>maxCost;
cout<<"Введите количесто вершин графа:\n";
cin>>kolVer;
 
// Записываем в cost вес ребер с помощью матрицы смежности
cout<<"Введите матрицу смежности:\n";
for (i=1; i<=kolVer; i++)
{
    for (j=1; j<=kolVer; j++)
    {
        cin>>cost[i][j];
        if (cost[i][j]==0)
        {cost[i][j]=maxCost;}
    }
}
 
creatFile(maxCost,kolVer,cost);
poiskMinOstDer(maxCost, kolVer, cost);
 
 
system("pause");
return 0;
};

При вводе значений например
Макс вес ребра: 5
Кол-во вершин: 2
матрица смежности:
0 1
1 0
И любое название файла, выводит:
Файл создан.
1 --> 0(все верное, кроме этого нуля)
Мин стоимость: 1

при вводе большего количества ребер или значения первого элемента не равным нулю, программа доходит до вывода надписи "Файл создан", а дальше останавливается... Не пойму в чем проблема...

Добавлено через 26 минут
Простите, остОвного дерева.

Добавлено через 2 часа 15 минут
убрал цикл while. Осталась проблема что после "1 --> ..." всегда выводятся нули.

Добавлено через 11 часов 25 минут
Немного изменил алгоритм функции, на

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
...
for (i=1; i<=kolVer; i++)
{
    for (j=1; j<=kolVer; j++)
    {
        if (cost[i][j]<min) 
        {
            if (used[i]==true)
            {
                min=cost[i][j];
                i2=i3=i;
                j2=j3=j;
            }
        }
        
        if (used[i3]==false || used[j3]==false)
        {
            rebro[iRebra]=j2;
            iRebra++;
            minCost=minCost+min;
            used[j2]=true;
        }
        cost[i2][j2]=cost[j2][i2]=maxCost;
        
    }
}
 
...

Теперь выскакивает ошибка "Unhandled exception at 0x008b10d8 in {НазваниеПроэкта}.exe: 0xC0000005: Access violation reading location 0x750aa5e5."

ругается на строчку

C++
1
    if (used[i3]==false || used[j3]==false)

а конкретнее мне кажется на переменную j2. Помогите пожалуйста, всю голову уже сломал.

@frEEze00 · 10.08.2014, 20:58 **[ТС]**

Сообщение от ya_noob

на каком-то шаге 50 вершин уже находятся в MST

по идее на каждом шаге добавляется вершина, поскольку у нас цикл от 0(1ой вершины) до kolVer(количества вершин)

Сообщение от ya_noob

по какой строке матрицы ты хочешь пройтись, чтобы выбрать из этих кандидатов вершину с наименьшей стоимостью ребра?

по той, которую еще не использовал, за использование отвечает used[]. По-моему так.

и да, программа которую я нашел в интернете(скидывал сюда ранее) работает... вот в ней я и разбираюсь. Запихнул я ее в функцию, переименовал переменные, чтобы было удобнее. Одну переменную взял другого типа( bool used[]), но у меня она не работает.

Так же написал функцию создающую текстовый файл, в котором будут храниться ранее введенные данные. Позже хочу еще написать функцию чтобы можно было выбрать из этих файлов нужный и использовать его(но там у меня проблема возникла в выводе списка файлов определенного расширения из каталога.. не хватает знаний)
Но это всё позже. Сейчас нужно отдохнуть. А то я уже часов 20 за два дня потратил на это задание.

@ya_noob · 10.08.2014, 21:42

Сообщение от frEEze00

и да, программа которую я нашел в интернете(скидывал сюда ранее) работает... вот в ней я и разбираюсь.

та, которая в 3-м сообщении что-ли?
работает? щас прям. вот попробуй с этой матрицей:

у меня выводит следующее:

C++
1
2
1 -> 3 -> 2 -> 4 -> 5
 Минимальная стоимость 11

нет там ребра 3->2. нифига она не работает.

Сообщение от frEEze00

по той, которую еще не использовал, за использование отвечает used[].

вот тут у тебя проблемы с пониманием алгоритма. правильный ответ: ни по какой. Кандидаты на добавление в MST на следующем шаге могут быть смежными с любой вершиной, уже находящейся в MST, а пробегаясь по строке мы сможем перебрать вершины, смежные только с этой вершиной.

итак, алгоритм Прима: перед очередным шагом алгоритма несколько вершин уже находятся в MST. на этом шаге проверяются все вершины, смежные с вершинами в MST, и выбирается наименьшая, которая и добавляется в MST на этом шаге. если смежных вершин не осталось, то алгоритм завершается. вот и весь алгоритм. ах да, перед первым шагом надо добавить в (пустое пока) MST одну вершины (у тебя это вершина 1: used[1]=true).

что мы имеем. а имеем мы (1) вершины, которые находятся в MST, (2) вершины, смежные с вершинами в MST (одна из них добавляется в MST на каком-то шагу) и (3) вершины, не смежные с MST (они не могут попасть в MST, не попав вначале в (2) ). вот с различением вершин (2) и вершин (3) у тебя проблемы. нельзя пробежаться по строке матрицы и даже по всей матрице в поисках очередной вершины. там могут встретиться как вершины из 2-й группы так и из 3-ей, а третью группу нельзя использовать.

@frEEze00 · 13.08.2014, 02:40 **[ТС]**

Сообщение от ya_noob

нет там ребра 3->2. нифига она не работает.

у меня переделанная выводит другое,

C++
1
2
1 -> 3 -> 5 -> 4 -> 0
Минимальная стоимость 11.

Стоимость выводит правильно вроде, а вот с вершинами проблема.. просчитывается только один путь(в данном случае, дошел до 4 вершины и затупил), то есть добрались до ближайшей, и дальше ищем расстояние до ближайшей от нее, не учитывая расстояние от первой вершины до второй ближайшей к ней(нагородил то). Пока не знаю, как реализовать это.

@ya_noob · 13.08.2014, 19:47

frEEze00, что ты так уцепился за ту программу. не будет она правильно работать. там нет реализации алгоритма Прима даже близко. самый лучший вариант начать писать всё заново. в предыдущем посте я тебе расписал как работает алгоритм (спрашивай, если что-то непонятно). единственная проблема там: "как эффективно хранить вершины из группы (2)".

PS: может тебе ссылку дать на правильную реализацию или еще помучаешься

@frEEze00 · 13.08.2014, 20:25 **[ТС]**

Сообщение от ya_noob

может тебе ссылку дать на правильную реализацию или еще помучаешься

еще помучаюсь) спасибо)

@frEEze00 · 16.08.2014, 01:02 **[ТС]**

Сообщение от ya_noob

нет там ребра 3->2. нифига она не работает.

Разобрался я в этой программе, все верно там, алгоритм реализован правильно. Считает мин ост дерево тоже верно. Проблема в выводе ребер. например граф
0 1 1 1
1 0 5 5
1 5 0 5
1 5 5 0

Минимальное дерево:3 (все верно)
а вывести он должен не одну строку типа

C++
1
1 -> 2 -> 3 -> 4

а три строки:

C++
1
2
3
1 -> 2
1 -> 3
1 -> 4

Там это не предусмотрено.

Добавлено через 34 минуты
Всё доделал, все работает. Если кому интересно, то вот:

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
#include <iostream>;
#include <fstream>;
 
 
using namespace std;
 
void creatFile(int maxCost, int kolVer, int **cost){
    //функция, создающая текстовый файл с заданным названием и записывающая в него данные для хранения
    int i,j;
    char name[50];
    cout<<"Введите название файла:";
    cin >> name;
    strcat(name, ".txt");
    ofstream out(name);
    out<<maxCost<<"\n"; //Записываем в первую строку файла максимальный вес ребра
    out<<kolVer<<"\n";  //Записываем во вторую строку количество вершин
 
    //в следующии строки записываем матрицу смежности
for (i=0; i<kolVer; i++)
{   
    for (j=0; j<kolVer; j++)
    {   
        out<<cost[i][j]<<" ";
    }
    out<<"\n";
}
 
    out.close();
    cout<<"Файл создан\n";
};
void poiskMinOstDer(int maxCost, int kolVer, int **cost)
{   
//Функциия поиска минимального оставного дерева на графе
int min;
int minCost=0;
int i,i2,i3;
int j,j2,j3;
int shet=1,iRebra=0;
bool used[10]={false};
used[1]=true;
int rebro[99]={0};
 
while (shet<kolVer){
for (i=1,min=maxCost; i<=kolVer; i++)
{   
    for (j=1; j<=kolVer; j++)
    {
        if (cost[i][j]<min) 
        {
            if (used[i]!=false)
            {
            min=cost[i][j];
            i2=i3=i;
            j2=j3=j;
            }
        }
    }
}
    if (used[i3]==false || used[j3]==false)
    {
        rebro[iRebra]=j2;
        cout<<"\n Из "<<i2<<" вершины в "<<j2<<" вершину, ребро="<<min;
        iRebra++;
        shet++;
        minCost=minCost+min;
        used[j2]=true;
    }
 
    cost[i2][j2]=cost[j2][i2]=maxCost;
}
cout<<"\n";
cout<<"\n Минимальная стоимость: "<<minCost;
cout<<"\n";
};
int main(){
setlocale (LC_ALL, "RUS");
int i,j;
int maxCost=100; //Максимальный вес ребра
int kolVer; //Количество вершин графа
int **cost;
cost = new int *[99];
for (i=1; i<=99; i++){cost[i]=new int[99];}  
 
 
cout<<"Введите максимальный вес ребра:\n";
cin>>maxCost;
cout<<"Введите количесто вершин графа:\n";
cin>>kolVer;
 
// Записываем в cost вес ребер с помощью матрицы смежности
cout<<"Введите матрицу смежности:\n";
for (i=1; i<=kolVer; i++)
{
    for (j=1; j<=kolVer; j++)
    {
        cin>>cost[i][j];
        if (cost[i][j]==0){cost[i][j]=maxCost;}
    }
}
 
//creatFile(maxCost,kolVer,cost);
poiskMinOstDer(maxCost, kolVer, cost);
 
 
system("pause");
return 0;
};

@ZaMaZaN4iK · 16.08.2014, 02:09

Я не знаю конечно, но может вам будет интересно это. Это алгоритм нахождения минимального остовного дерева алгоритмом Крускала (список рёбер):

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
//Минимальное остовное дерево за O(NlogN) методом Краскала через DSU(систему непересекающихся множеств)
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <ctime>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
const ll maxn=100,maxm=200;//максимум вершин и максимум рёбер
vector<ll> d(maxn,-1);//массив для DSU
vector<pair<ll,pair<ll,ll> > > a(maxm),p;//тут будем хранить рёбра.Первый элемент - вес ребра, 2-ой и 3-ий - начало и конец ребра
ll i,j,k,z=0,temp,r,n,m;
 
//функция для получения корня данного множества.Подробное описание в описании самого DSU
 
ll findroot(ll v)
{
    return d[v]==-1 ? v : d[v]=findroot(d[v]);
}
 
//функция обьединения двух множеств.Подробное описание в описании самого DSU
 
bool union_set(ll a,ll b)
{
    ll q1,q2;
    q1=findroot(a);
    q2=findroot(b);
    if(q1 != q2)
    {
        r=rand() % 2;
        r==0 ? d[q1]=q2 : d[q2]=q1;
        return true;
    }
    return false;
}
 
//Задаем граф по кторому будем искать минимальный остов
 
void input()
{
    scanf("%I64d %I64d",&n,&m);
    for(i=0;i<m;++i)
    {
        scanf("%I64d %I64d %I64d",&a[i].second.first,&a[i].second.second,&a[i].first);
    }
}
 
//Главная функция алгоритма.Работает следующим образом: мы сортируем в порядке возрастания ребра по весу.Потом берем первые n-1 рёбер
//(так как дерево будет состоять из n-1 ребра по теореме о деревьях) и если концы не принадлежат одному множеству(то есть не соединены), то берем это ребро
//добавлем вес к минимальной стоимости дерева, и обьединяем концы ребра в одно множество.И так до тех пор, пока не запишем в ответ N-1 раз ребра.
//В данной реализации мы не минимальный вес получаем, а сами ребра, из которых будет состоять мимнимальное остовное дерево
 
void sol()
{
    sort(a.begin(),a.begin()+m);
    temp=n-1;
    for(i=0;i<m && z<temp;++i)
    {
        if(union_set(a[i].second.first,a[i].second.second))
        {
            ++z;
            p.push_back(a[i]);
        }
    }
}
 
//Вывод полученного дерева
 
void output()
{
    for(i=0;i<p.size();++i)
        printf("%I64d -> %I64d = %I64d\n",p[i].second.first,p[i].second.second,p[i].first);
}
 
//Ну а тут сначала обнуляем rand(), затем вводим граф, считаем min_ost и выводим его
 
int main()
{
    srand(time(0));
    input();
    sol();  
    output();  
    system("pause");
    return 0;
}

@ya_noob · 16.08.2014, 08:23

Сообщение от frEEze00

Всё доделал, все работает.

ну давай поглядим:
1. строка 19: цикл инициализирует строки с 0 по kolVer - 1,
а строка 44: цикл уже бегает по строкам с 1 по kolVer, т.е. программа лезет за пределы своей памяти. Ошибка!

2. вернемся к нашим баранам: еще раз говорю "Это не алгоритма Прима". Я могу согласиться, что твоя прога будет работать правильно, если ее маленько допилить, т.к. ты реализовал (!) алгоритм Буровки (хоть и не эффективный). Возникает вопрос: Какого х... ты пудрил мне мозги про Приму:

Сообщение от frEEze00

И да, мечусь, пробую все варианты, может и заработает. Поиск минимального остовного дерева, алгоритм Прима. В алгоритме я уже давно разобрался. С реализацией возникли проблемы ...

если сам писал Буровку. у этих алгоритмов совершенно разный подход!!!
Возьми умную книжку по алгоритмам и садись разбирайся заново. У Седжвика, например, есть описание обоих этих алгоритмов.

Новые блоги и статьи Все статьи Все блоги /
GitHub Copilot в JetBrains: модель по умолчанию, Fix и контроль MCP and_y87 12.10.2026 10 октября 2026 года GitHub обновил Copilot для JetBrains: добавил настройки стартовой модели, исправления из диагностики и управление автозапуском MCP. Поддержка IDE 2025. 1 прекращена — требуется. . .	День 5 из 28: Codex подсказывает следующий запрос and_y87 12.10.2026 9 октября 2026 года OpenAI запустила бету Composer predictions — подсказок следующего сообщения в текущем диалоге Codex. Это помощь с формулировкой запроса, а не автоматическое продолжение задачи. . . .	Запустил конкурс "тем и промптов для текстовых квестов созданных почти чисто ИИ" Adler 06.10.2026 Всем привет! За последние три-четыре дня я создал более 16 текстовых квестовых игр используя преимущественно по одному запросу к ИИ на игру. Мне так понравилось смотреть все ветки/ сцены во всех. . .	ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .
Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .

@ya_noob _ 317 / 151 / 27 Регистрация: 08.10.2011 Сообщений: 432
	13.08.2014, 19:47
	frEEze00, что ты так уцепился за ту программу. не будет она правильно работать. там нет реализации алгоритма Прима даже близко. самый лучший вариант начать писать всё заново. в предыдущем посте я тебе расписал как работает алгоритм (спрашивай, если что-то непонятно). единственная проблема там: "как эффективно хранить вершины из группы (2)". PS: может тебе ссылку дать на правильную реализацию или еще помучаешься 0