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

Алгоритм для деревьев - C++

Восстановить пароль Регистрация
 
html-profi
5 / 5 / 0
Регистрация: 25.11.2011
Сообщений: 53
12.04.2012, 21:45     Алгоритм для деревьев #1
Всем привет!
Препод дал задание написать программу, которая бы находила максимальное независимое множество в дереве(т.е. дано дерево, надо найти максимальное множество вершин, никакие две из которых не связаны ребром)
Нашел на псевдокод
function get_independent_set(Node u)
{
если I(u) уже посчитано, то возвратить I(u)
//мощность множества, которое можно получить, если не брать вершину u
children_sum = 0
//мощность множества, которое можно получить, если взять вершину u
grandchildren_sum = 0
//цикл по всем детям
for i := 1 to child_num do
children_sum = children_sum + get_independent_set(children[i])
//цикл по всем внукам
for i:= 1 to grandchildren_num
grandchildren_sum = grandchildren_sum + get_independent_set(grandchildren[i])
//запоминаем, чтобы не персчитывать ещё раз
I(u) = max(1 + grandchildren_sum, children_sum)
возвратить I(u)
}

но ничего не пойму. Помогите плиз.
Буду благодарен за помощь.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.04.2012, 21:45     Алгоритм для деревьев
Посмотрите здесь:

Слияние деревьев C++
C++ Объединение 2-х бинарных деревьев в одно
Есть у кого исходники 2-3-4 деревьев? C++
Помогите алгоритм для char переделать в алгоритм для float C++
C++ Массив: Учащиеся участвовали в посадке деревьев. Сколько деревьев было посажено
C++ Сравнить структуру двух деревьев
турнирная сортировка деревьев C++
Класс бинарных деревьев. Наследование C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

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