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

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

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

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

08.10.2015, 19:06. Просмотров 308. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.10.2015, 19:06
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Прима (C++):

Алгоритм Прима! - C++
И снова здравствуйте! Ознакомился с алгоритмом прима, видел псевдокод, решал примеры, но вот задался вопросом, как реализовать данный...

Алгоритм прима - C++
Всем привет! Помогите пожалуйста реализовать алгоритм Прима, для нахождения минимального остового графа! Сам метод мне известен,...

Графы. Алгоритм Прима - C++
Начал изучать графы и в месте с ними алгоритм Прима. Суть понял, но разобрать(понять) реализацию на с++ не получилось. решил написать...

Правильный вывод. Алгоритм Прима - C++
Здравствуйте есть код, нужно изменить вывод. #include&lt;conio.h&gt; #include&lt;iostream&gt; using namespace std; int a,b,u,v,n,i,j,ne=1; ...

Алгоритм Прима. Минимальное островное дерево - C++
Всем доброго времени суток. Сейчас нахожусь в полной фрустрации, т.к уже пару часов не могу найти исходник алгоритма Прима на С++. Сам...

Алгоритм Прима для построения максимального дерева - C++
Алгоритм Прима.С++

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.10.2015, 19:06
Привет! Вот еще темы с ответами:

Реализовать алгоритм Прима с бинарной кучей, в которой нужно хранить ребра - C++
Здравствуйте уважаемые программисты тут вот такая задачка попалась нужно реализовать алгоритм Прима с бинарной кучей, в которой нужно...

Реализация алгоритма Прима - C++
Алгоритм Прима?кто может написать?

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...


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

Или воспользуйтесь поиском по форуму:
1
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.