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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Вычисление минимального числа из М чисел http://www.cyberforum.ru/cpp-beginners/thread204049.html
Помогите пожалуйста... Задание звучит так:"Вычислите минимальное из М чисел, где М задается в виде параметра функции."
C++ Исправить ошибку в тексте Я новичок в программировании. Помогите пожалуйста в решении задачи: Ввести строку. Если встречается ошибка "жы" или "шы", исправить. Я пыталась решить так char S; int i; puts ("Vvedite text ");... http://www.cyberforum.ru/cpp-beginners/thread204046.html
C++ структуры
друзья, помогите оформить програму. мне задали несколько заданий, я их выполнил, но как ето функцыями записать, тоесть в одной програме, для меня проблематично #include "stdafx.h" #include...
C++ Считать текст из файла и вывести на экран только предложения, не содержащие запятых
Здравствуйте. Прошу помощи в написание программу на C++ "Написать программу, которая считывает текст из файла и выводит на экран только предложения, не содержащие запятых." Заранее благодарен. Я...
C++ В матрице найти произведение над главной диагональю,если произведение делится на 3 заменить побочную диагональ 0. http://www.cyberforum.ru/cpp-beginners/thread204034.html
Нужно заменить элементы побочной диагонали нулями,если произведение парных элементов над главной диагональю делится на 3,все сделал кроме замены элементов побочной диагонали нулями,если не сложно...
C++ Делаю текстовую пошаговую стратегию по bluetooth!!! Уменя такая идея-сделать текстовую пошаговую стратегию по bluetooth:jokingly: расчитанной на два игрока хотя бы. Помогите найти книги/статьи на тему Bluetooth сервер+клиент.. ну естественно на C++... подробнее

Показать сообщение отдельно
SaufeR
0 / 0 / 0
Регистрация: 19.12.2009
Сообщений: 10

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

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

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

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

1. Изначально, пусть T — пустое множество ребер (представляющее собой остовный лес, в который каждая вершина входит в качестве отдельного дерева).
2. Пока T не является деревом (что эквивалентно условию: пока число рёбер в T меньше, чем V − 1, где V — число вершин в графе):
* Для каждой компоненты связности (то есть, дерева в остовном лесе) в подграфе с рёбрами T, найдём самое дешёвое ребро, связывающее эту компоненту с некоторой другой компонентой связности. (Предполагается, что веса рёбер различны, или как-то дополнительно упорядочены так, чтобы всегда можно было найти единственное ребро с минимальным весом).
* Добавим все найденные рёбра в множество T.
3. Полученное множество рёбер T является минимальным остовным деревом входного графа.
Буду благодарен за любые наброски или любой код, даже с ошибками, так как реально не знаю с чего начать.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.