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

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

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

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

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

Дан полный взвешенный граф, кол-во вершин задается пользователем, вес ребер рандомный от 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++
Найти минимальное и максимальное из трех введенных чисел a, b, c. Написал: #include <stdio.h> #include <conio.h> #include...

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

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

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

Найти минимальное в произведении чисел - C++
Ребята помогите, т. к. что то не пойму! Нужно найти минимальное в произведении чисел!!!! # include <iostream> # include <ctime> ...

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

Найти минимальное значение функции - C++
Найти минимальное значение функции y = a*exp(-b*x)*cos(w*x + f); a = 19.5; b = 0.5; w = 4.5; f = 0.448; Как найти минимальное...

Найти максимальное и минимальное значение - C++
Задание элементарное, только никак не могу догадаться. На ввод N раз идет целое число s, нужно найти среди всех введенных чисел...

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

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


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

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

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