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

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

Восстановить пароль Регистрация
 
bez
0 / 0 / 0
Регистрация: 04.07.2014
Сообщений: 83
08.10.2015, 19:06     Алгоритм Прима #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
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);
    }
Может у кого есть готовый рабочий вариант алгоритма прима на списках смежности или помогите разобраться с этим
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.10.2015, 19:06     Алгоритм Прима
Посмотрите здесь:

C++ c++/алгоритм
C++ Алгоритм прима
алгоритм C++
алгоритм C++
Алгоритм C++
C++ Алгоритм Прима!
C++ Реализовать алгоритм Прима с бинарной кучей, в которой нужно хранить ребра
C++ Графы. Алгоритм Прима

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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