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

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

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

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

30.05.2013, 17:02. Просмотров 604. Ответов 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 и что в вайле происходит
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
30.05.2013, 17:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск минимального остовного дерева в графе (C++):

Поиск минимального остовного дерева на графе - C++
Переделал программу найденную в интернете, написал через функцию. #include &lt;iostream&gt;; #include &lt;fstream&gt;; using namespace...

Поиск минимального остовного дерева на графе - C++
Доброго времени суток, не могу уже несколько дней сделать лабораторку по дискретной математике Дан граф (скрин ниже будет), для проги на...

Визуализация построения минимального остовного дерева - C++
Помогите написать код для визуализации построения минимального остовного дерева (алгоритм Краскала). Заданы координаты вершин графов, нужно...

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

Поиск значения минимального листа дерева/ошибка - C++
всем привет, такая проблема: в чем ошибка поиска значения минимального листа? #include &lt;tchar.h&gt; #include &lt;stdio.h&gt; #include...

Поиск минимального элемента идеально сбалансированного дерева - C++
Как найти минимальный элемент? Вообще не представляю. зы. Дерево поиска другой разговор.

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
30.05.2013, 17:02
Привет! Вот еще темы с ответами:

Поиск остовного леса методом Соллина - C++
Доброго времени суток. Передо мной встала задача найти остовной лес минимальной стоимости методом Соллина. Интернет предложил единственный...

Поиск циклов в графе. Поиск центра взвешенного графа - C++
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?

Поиск на графе - C++
Доброго времени суток. Мне не совсем понятна реализация в коде поиска на графе в высоту и ширину. Т.к. в книге они описаны не совсем...

Поиск ободов в графе - C++
К сожалению не получается решить эту задачу на Си. Вот исходный текст задачи: &quot;Найти в графе все подграфы, которые являются ободами&quot;. ...


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

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

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