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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Не компилируются проекты: Build: 0 succeeded, 1 failed, 0 up-to-date, 0 skipped http://www.cyberforum.ru/cpp-beginners/thread1240571.html
Здравствуйте, уважаемые специалисты. Недавно начал изучать С++ Компилятор Visual C++ при попытке скомпилировать любой код выдаёт это: ========== Build: 0 succeeded, 1 failed, 0 up-to-date, 0...
C++ Конструктор копирования, аварийное завершение на этапе исполнения #include <iostream.h> #include <string.h> class String{ private: char *data; int max_length; public: String() { http://www.cyberforum.ru/cpp-beginners/thread1240568.html
C++ Будут ли все константы гарантированно инициализированы к моменту обращения к ним из разных единиц трансляции
Безопасно ли такое использование: // config.cpp const int ival = 6; const SomeNonTrivialClass obj(...); // config.h extern const int ival; extern const SomeNonTrivialClass obj; //...
Как реализовать свой тип данных C++
Здравсвтуйте,подскажите пожалуйста как реализовать с с++ свой тип данных. Допустим хочу завести массив,где каждому arr будет соответсвовать две переменные(arr.a,arr.b). Если точнее - arr.a,arr.b ......
C++ Перегруженный operator<< http://www.cyberforum.ru/cpp-beginners/thread1240484.html
Есть допустим такая дружественная функция: объявление template<typename Type> friend std::ostream& operator<<(std::ostream&, Stack<Type>&); определение template<typename Type> std::ostream&...
C++ Вывести на экран суммарный результат, указав число студентов сдавших и проваливших экзамен День добрый помогите решить задачу: есть 10 студентов ( 10 раз на екран должно высвечиватся"Введите результат" результат- если пользователь пишет 1,значит студент сдал,если пишет 2 - провалил... подробнее

Показать сообщение отдельно
frEEze00
2 / 2 / 1
Регистрация: 10.07.2014
Сообщений: 25

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

10.08.2014, 15:22. Просмотров 4205. Ответов 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
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. Помогите пожалуйста, всю голову уже сломал.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.