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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
bez
0 / 0 / 0
Регистрация: 04.07.2014
Сообщений: 83
#1

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

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

Алгоритм Брезенхэма C++
C++ Алгоритм Евклида
C++ Алгоритм прима
C++ Алгоритм Прима!
C++ Волновой алгоритм
C++ Реализовать алгоритм Прима с бинарной кучей, в которой нужно хранить ребра
C++ Алгоритм Джарвиса
C++ Графы. Алгоритм Прима
Алгоритм Форда C++
Жадный алгоритм C++
Алгоритм Прима для построения максимального дерева C++
Алгоритм Прима. Минимальное островное дерево C++

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

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

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