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

Поиск минимального остовного дерева на графе - 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
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;
};
0
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru