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

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

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

Поиск минимального остовного дерева в графе - C++

30.05.2013, 17:02. Просмотров 561. Ответов 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
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
#include <vector>
#include <queue> // Определяет классы priority_queue шаблона и очереди и несколько 
вспомогательных шаблонов
#include <iostream>
using namespace std;
 
typedef pair<int, int> a; //pair - список смежности хранящий, вершины; a - вес ребра
typedef vector<vector<a>> Graph;
 
long long func(Graph &g, vector<int> &pred) //
{
    int inf = 10000000;
    int n = g.size();
    pred.assign(n, -1);
    vector<bool> used(n); //вектор, использованных вершин
    vector<int> vector_rast(n, inf); //вектор расстояний
    vector_rast[0] = 0;
    priority_queue <a, vector<a> , greater<a>> q;
    q.push(make_pair(0, 0));
    long long res = 0;
 
    while (!q.empty()) {
        int start = q.top().first;
        int end = q.top().second;
        q.pop();
        if (used[end])
            continue;
        used[end] = true;
        res += start;
        for (int i=0; i<(int)g[end].size(); i++)
        {
            int v = g[end][i].first; //выбраем ребро из дерева в цикл с наименьшим весом
            if (used[v])
                continue;
            int vector_rast2 = g[end][i].second; //добавляем конец ребра к дереву
            if (vector_rast[v] > vector_rast2) { //изменяем цикл, для этого обновляем 
список ребер из дерева в цикле так, чтобы он состоял из ребер наименьшего веса
                vector_rast[v] = vector_rast2;
                pred[v] = end;
                q.push(make_pair(vector_rast2, v)); //добавляем в цикл вершины, соседние 
с новой
            }
        }
    }
    return res;
}
 
void main()
{
    setlocale (LC_ALL, "Russian");
        Graph g(5);
    g[0].push_back(make_pair(2, 4));
    g[2].push_back(make_pair(0, 4));
    g[0].push_back(make_pair(4, 7));
    g[4].push_back(make_pair(0, 7));
    g[1].push_back(make_pair(2, 4));
    g[2].push_back(make_pair(1, 4));
    g[2].push_back(make_pair(3, 5));
    g[3].push_back(make_pair(2, 5));
 
    Изменение:
    g[0].push_back(make_pair(2, 4));
    g[2].push_back(make_pair(0, 4));
    g[3].push_back(make_pair(4, 6));
    g[4].push_back(make_pair(3, 6));
    g[1].push_back(make_pair(2, 4));
    g[2].push_back(make_pair(1, 4));
    g[2].push_back(make_pair(3, 5));
    g[3].push_back(make_pair(2, 5));
 
    Конечный вариант:
    g[0].push_back(make_pair(2, 4));
    g[2].push_back(make_pair(0, 4));
    g[0].push_back(make_pair(1, 3));
    g[1].push_back(make_pair(0, 3));
    g[0].push_back(make_pair(3, 2));
    g[3].push_back(make_pair(0, 2));
    g[1].push_back(make_pair(4, 3));
    g[4].push_back(make_pair(1, 3));
 
    vector<int> vector_rast;
    long long result = func(g, vector_rast);
    cout << "Результат: " << result << endl;
    system("pause");
}
Добавлено через 5 минут
Помогите разобраться с кодом. Конкретно: для чего нужен pred.assign и что в вайле происходит
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.05.2013, 17:02     Поиск минимального остовного дерева в графе
Посмотрите здесь:

C++ Поиск ободов в графе
C++ Поиск циклов в графе
Поиск на графе C++
C++ Поиск минимального элемента идеально сбалансированного дерева
C++ Поиск в ширину на графе
Поиск остовного леса методом Соллина C++
Поиск циклов в графе. Поиск центра взвешенного графа C++
C++ Визуализация построения минимального остовного дерева
C++ Поиск минимального листа дерева
Поиск значения минимального листа дерева/ошибка C++
C++ Поиск минимального остовного дерева на графе
C++ Поиск мостов в графе

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

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

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