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

Найти минимальное остовное дерево - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.89
SaufeR
0 / 0 / 0
Регистрация: 19.12.2009
Сообщений: 10
05.12.2010, 19:26     Найти минимальное остовное дерево #1
Дан полный взвешенный граф, кол-во вершин задается пользователем, вес ребер рандомный от 1 до 100. Найти минимальное остовное дерево при помощи алгоритма представленного ниже.
Алгоритм
Работа алгоритма состоит из нескольких итераций, каждая из которых состоит в последовательном добавлении рёбер к остовному лесу графа, до тех пор, пока лес не превратится в дерево, то есть, лес, состоящий из одной компоненты связности.

В псевдокоде, алгоритм можно описать так:

1. Изначально, пусть T — пустое множество ребер (представляющее собой остовный лес, в который каждая вершина входит в качестве отдельного дерева).
2. Пока T не является деревом (что эквивалентно условию: пока число рёбер в T меньше, чем V − 1, где V — число вершин в графе):
* Для каждой компоненты связности (то есть, дерева в остовном лесе) в подграфе с рёбрами T, найдём самое дешёвое ребро, связывающее эту компоненту с некоторой другой компонентой связности. (Предполагается, что веса рёбер различны, или как-то дополнительно упорядочены так, чтобы всегда можно было найти единственное ребро с минимальным весом).
* Добавим все найденные рёбра в множество T.
3. Полученное множество рёбер T является минимальным остовным деревом входного графа.
Буду благодарен за любые наброски или любой код, даже с ошибками, так как реально не знаю с чего начать.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.12.2010, 19:26     Найти минимальное остовное дерево
Посмотрите здесь:

найти минимальное и максимальное C++
C++ Найти минимальное число
C++ Найти минимальное из чисел
C++ Найти минимальное положительное число.
C++ Массивы. Посчитать количество положительных, найти минимальное, удалить строку с минимальным (Не могу найти ошибку)
C++ Найти минимальное и максимальное
C++ Найти минимальное в произведении чисел
Построить для заданного графа минимальное основное дерево C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
05.12.2010, 20:02     Найти минимальное остовное дерево #2
Каким образом у вас в программе "дан полный взвешенный граф"?
SaufeR
0 / 0 / 0
Регистрация: 19.12.2009
Сообщений: 10
05.12.2010, 20:04  [ТС]     Найти минимальное остовное дерево #3
В виде матрицы смежности.
Yandex
Объявления
05.12.2010, 20:04     Найти минимальное остовное дерево
Ответ Создать тему
Опции темы

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