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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.70
frEEze00
2 / 2 / 1
Регистрация: 10.07.2014
Сообщений: 25
10.08.2014, 15:22     Поиск минимального остовного дерева на графе #1
Переделал программу найденную в интернете, написал через функцию.
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. Помогите пожалуйста, всю голову уже сломал.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.08.2014, 15:22     Поиск минимального остовного дерева на графе
Посмотрите здесь:

C++ поиск циклов в графе
Поиск на графе C++
C++ Поиск минимального элемента идеально сбалансированного дерева
Поиск остовного леса методом Соллина C++
Поиск циклов в графе. Поиск центра взвешенного графа C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
frEEze00
2 / 2 / 1
Регистрация: 10.07.2014
Сообщений: 25
10.08.2014, 20:58  [ТС]     Поиск минимального остовного дерева на графе #21
Цитата Сообщение от ya_noob Посмотреть сообщение
на каком-то шаге 50 вершин уже находятся в MST
по идее на каждом шаге добавляется вершина, поскольку у нас цикл от 0(1ой вершины) до kolVer(количества вершин)
Цитата Сообщение от ya_noob Посмотреть сообщение
по какой строке матрицы ты хочешь пройтись, чтобы выбрать из этих кандидатов вершину с наименьшей стоимостью ребра?
по той, которую еще не использовал, за использование отвечает used[]. По-моему так.

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

Так же написал функцию создающую текстовый файл, в котором будут храниться ранее введенные данные. Позже хочу еще написать функцию чтобы можно было выбрать из этих файлов нужный и использовать его(но там у меня проблема возникла в выводе списка файлов определенного расширения из каталога.. не хватает знаний)
Но это всё позже. Сейчас нужно отдохнуть. А то я уже часов 20 за два дня потратил на это задание.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
10.08.2014, 21:42     Поиск минимального остовного дерева на графе #22
Цитата Сообщение от frEEze00 Посмотреть сообщение
и да, программа которую я нашел в интернете(скидывал сюда ранее) работает... вот в ней я и разбираюсь.
та, которая в 3-м сообщении что-ли?
работает? щас прям. вот попробуй с этой матрицей:
C++
1
2
3
4
5
6
5
0 5 2 0 0
5 0 0 3 0
2 0 0 0 8
0 3 0 0 1
0 0 8 1 0
у меня выводит следующее:
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
2 / 2 / 1
Регистрация: 10.07.2014
Сообщений: 25
13.08.2014, 02:40  [ТС]     Поиск минимального остовного дерева на графе #23
Цитата Сообщение от ya_noob Посмотреть сообщение
нет там ребра 3->2. нифига она не работает.
у меня переделанная выводит другое,

C++
1
2
1 -> 3 -> 5 -> 4 -> 0
Минимальная стоимость 11.
Стоимость выводит правильно вроде, а вот с вершинами проблема.. просчитывается только один путь(в данном случае, дошел до 4 вершины и затупил), то есть добрались до ближайшей, и дальше ищем расстояние до ближайшей от нее, не учитывая расстояние от первой вершины до второй ближайшей к ней(нагородил то). Пока не знаю, как реализовать это.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
13.08.2014, 19:47     Поиск минимального остовного дерева на графе #24
frEEze00, что ты так уцепился за ту программу. не будет она правильно работать. там нет реализации алгоритма Прима даже близко. самый лучший вариант начать писать всё заново. в предыдущем посте я тебе расписал как работает алгоритм (спрашивай, если что-то непонятно). единственная проблема там: "как эффективно хранить вершины из группы (2)".

PS: может тебе ссылку дать на правильную реализацию или еще помучаешься
frEEze00
2 / 2 / 1
Регистрация: 10.07.2014
Сообщений: 25
13.08.2014, 20:25  [ТС]     Поиск минимального остовного дерева на графе #25
Цитата Сообщение от ya_noob Посмотреть сообщение
может тебе ссылку дать на правильную реализацию или еще помучаешься
еще помучаюсь) спасибо)
frEEze00
2 / 2 / 1
Регистрация: 10.07.2014
Сообщений: 25
16.08.2014, 01:02  [ТС]     Поиск минимального остовного дерева на графе #26
Цитата Сообщение от 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
Мой лучший друг-отладчик!
 Аватар для ZaMaZaN4iK
163 / 163 / 9
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
Завершенные тесты: 1
16.08.2014, 02:09     Поиск минимального остовного дерева на графе #27
Я не знаю конечно, но может вам будет интересно это. Это алгоритм нахождения минимального остовного дерева алгоритмом Крускала (список рёбер):
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;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
16.08.2014, 08:23     Поиск минимального остовного дерева на графе
Еще ссылки по теме:

C++ Визуализация построения минимального остовного дерева
C++ Поиск минимального листа дерева
Поиск значения минимального листа дерева/ошибка C++

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

Или воспользуйтесь поиском по форуму:
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
16.08.2014, 08:23     Поиск минимального остовного дерева на графе #28
Цитата Сообщение от frEEze00 Посмотреть сообщение
Всё доделал, все работает.
ну давай поглядим:
1. строка 19: цикл инициализирует строки с 0 по kolVer - 1,
а строка 44: цикл уже бегает по строкам с 1 по kolVer, т.е. программа лезет за пределы своей памяти. Ошибка!

2. вернемся к нашим баранам: еще раз говорю "Это не алгоритма Прима". Я могу согласиться, что твоя прога будет работать правильно, если ее маленько допилить, т.к. ты реализовал (!) алгоритм Буровки (хоть и не эффективный). Возникает вопрос: Какого х... ты пудрил мне мозги про Приму:
Цитата Сообщение от frEEze00 Посмотреть сообщение
И да, мечусь, пробую все варианты, может и заработает. Поиск минимального остовного дерева, алгоритм Прима. В алгоритме я уже давно разобрался. С реализацией возникли проблемы ...
если сам писал Буровку. у этих алгоритмов совершенно разный подход!!!
Возьми умную книжку по алгоритмам и садись разбирайся заново. У Седжвика, например, есть описание обоих этих алгоритмов.
Yandex
Объявления
16.08.2014, 08:23     Поиск минимального остовного дерева на графе
Ответ Создать тему
Опции темы

Текущее время: 22:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru