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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.89
SaufeR
0 / 0 / 0
Регистрация: 19.12.2009
Сообщений: 10
#1

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

05.12.2010, 19:26. Просмотров 2406. Ответов 2
Метки нет (Все метки)

Дан полный взвешенный граф, кол-во вершин задается пользователем, вес ребер рандомный от 1 до 100. Найти минимальное остовное дерево при помощи алгоритма представленного ниже.
Алгоритм
Работа алгоритма состоит из нескольких итераций, каждая из которых состоит в последовательном добавлении рёбер к остовному лесу графа, до тех пор, пока лес не превратится в дерево, то есть, лес, состоящий из одной компоненты связности.

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

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

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

Построить для заданного графа минимальное основное дерево - C++
Построить для заданного графа минимальное основное дерево. Помогите на С++ написать задачку) Найти минимальный путь.

Массивы. Посчитать количество положительных, найти минимальное, удалить строку с минимальным (Не могу найти ошибку) - C++
// Заданы матрицы X(8;4),Y(5;5),Z(6;9). // Для каждой из матриц определить строку, в которой находится наименьшее // количество...

Найти минимальное число - C++
Вообщем есть 10 переменных.нужно найти какое из них наименьшее.С if слишком громоздко выходит

Найти минимальное и максимальное - C++
Найти минимальное и максимальное из трех введенных чисел a, b, c. Написал: #include <stdio.h> #include <conio.h> #include...

Найти минимальное из чисел - C++
Найти минимальное из чисел А В С сели А=sin(x) B=cos(x) C=ln/Х/

2
lemegeton
2931 / 1360 / 136
Регистрация: 29.11.2010
Сообщений: 2,725
05.12.2010, 20:02 #2
Каким образом у вас в программе "дан полный взвешенный граф"?
0
SaufeR
0 / 0 / 0
Регистрация: 19.12.2009
Сообщений: 10
05.12.2010, 20:04  [ТС] #3
В виде матрицы смежности.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.12.2010, 20:04
Привет! Вот еще темы с ответами:

найти минимальное и максимальное - C++
прошу помочь розобраться.. программа №1 создает файл с разными данными, зарплата, имя, и т.д.. программа №2 должна вывести минимально...

Найти минимальное значение в матрице - C++
Ввести в матрицу размером 3 на 4 числа.Найти минимальный элемент матрицы

Найти минимальное из введенных чисел - C++
1. Последовательно вводятся N целых чисел. Найти минимальное из них.

Найти минимальное значение массива - C++
Вот есть код: #include "stdafx.h" #include <algorithm> #include <iostream> #include <conio.h> using namespace std; ...


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

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

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