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

Алгоритм Прима - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Табулирование функции и выведение результата в таблице.Форматный вывод данных http://www.cyberforum.ru/cpp-beginners/thread1547628.html
Привет ребят, вообщем не знаю в чем проблема.Решал пример 4 #include <iostream> #include <cmath> using namespace std; int main() { double x,t,h,xn,xk,w; cout<<"t"<<endl;
C++ Вычислить и вывести на экран значение функции на заданном интервале Помогите Плиз))) задача во вложение. Ознакомьтесь, пожалуйста, с правилами форума. п. 5.18 Запрещено размещать задания и решения в виде картинок и других файлов с их текстом. Перепишите... http://www.cyberforum.ru/cpp-beginners/thread1547623.html
C++ В каких из приведенных ниже ситуаций может быть вызван конструктор копирования класса String:
1. String spaces(size_t n) { const String s(n, ' '); return s; } int main() { std::cout << spaces(10).str << "\n"; return 0;
C++ Требуется только объявить переменную, инициализировать ее не нужно
по модификатору const. Объявите переменную c именем m, в которой хранится указатель на двумерный массив целых чисел (int), выделенный в динамической памяти, так чтобы содержимое массива нельзя было...
C++ Подсчитать количество пар соседних элементов с одинаковыми знаками http://www.cyberforum.ru/cpp-beginners/thread1547611.html
Дан линейный массив из 11 целых чисел. Подсчитать количество пар соседних элементов, которые имеют одинаковые знаки. Спасибо за ранние.
C++ Какие из этих методов можно и стоит отметить как константные (имеется ввиду логическая константность) Пусть теперь класс String выглядит следующим образом: struct String { String(const char *str = ""); /* 1 */ String(size_t n, char c); /* 2 */ ~String(); ... подробнее

Показать сообщение отдельно
bez
0 / 0 / 0
Регистрация: 04.07.2014
Сообщений: 83

Алгоритм Прима - C++

08.10.2015, 19:06. Просмотров 309. Ответов 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
int n, m;
vector <pair<int, int>> g[24];//кроме вершин список смежности хранит и вес ребра
vector <bool> used(n, 0);//вектор использованных вершин
int inf = 10000000;
vector <int> d(m, inf);//вектор расстояний
int main()
{
    setlocale(LC_ALL, "Russian");
    fstream in;
    in.open("input.txt", ios::in);
    in >> n; //кол-во вершин
    in >> m; //количество ребер
    int x, y, l;
    pair <int, int> temp;
    for (int i = 0; i < m; i++){
        in >> x; //левая вершина
        in >> y; //правая вершина
        in >> l; //вес ребра
        x--;
        y--;
        temp.first = y;
        temp.second = l;
        g[x].push_back(temp);
        temp.first = x;
        g[y].push_back(temp);
    }
    vector <pair<int, int>> path(500);
    d[0] = 0;
    while (true){
        int v = -1;
        int dist = inf;
        forn(u, n)
        if (!used[u] && dist >= d[u])
        {
            v = u;
            dist = d[u];
        }
        if (v == -1) break;
        used[v] = true;
        forn(u, g[v].size())
        if (!used[g[v][u].first]) {
            if (d[g[v][u].first]>g[v][u].second) path[g[v][u].first] = make_pair(v, g[v][u].first);
            d[g[v][u].first] = min(d[g[v][u].first], g[v][u].second);
        }
    }
    long long sum = 0;
    forn(i, n) sum += d[i];
    cout << sum << endl;
    forn(i, n - 1)
        cout << path[i + 1].first + 1 << " " << path[i + 1].second + 1 << endl;
 
    return 0;
}
сделав отладку, заметил, что при добавлении список смежности заполняется не верно
косяк где-то в этом коде
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    fstream in;
    in.open("input.txt", ios::in);
    in >> n;
    in >> m;
    int x, y, l;
    pair <int, int> temp;
    for (int i = 0; i < m; i++){
        in >> x;
        in >> y;
        in >> l;
        x--;
        y--;
        temp.first = y;
        temp.second = l;
        g[x].push_back(temp);
        temp.first = x;
        g[y].push_back(temp);
    }
Может у кого есть готовый рабочий вариант алгоритма прима на списках смежности или помогите разобраться с этим
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.