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

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

Войти
Регистрация
Восстановить пароль
 
html-profi
5 / 5 / 0
Регистрация: 25.11.2011
Сообщений: 53
#1

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

12.04.2012, 21:45. Просмотров 892. Ответов 0
Метки нет (Все метки)

Всем привет!
Препод дал задание написать программу, которая бы находила максимальное независимое множество в дереве(т.е. дано дерево, надо найти максимальное множество вершин, никакие две из которых не связаны ребром)
Нашел на псевдокод
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++
C++ Объединение 2-х бинарных деревьев в одно
Есть у кого исходники 2-3-4 деревьев? C++
C++ Массив: Учащиеся участвовали в посадке деревьев. Сколько деревьев было посажено
C++ Определить, сколько посажено деревьев
C++ Вычисление глубины деревьев(нужна подсказка)
C++ контейнеры STL и виды деревьев
C++ Сравнить структуру двух деревьев
турнирная сортировка деревьев C++
Класс бинарных деревьев. Наследование C++
C++ Итеративная функция сравнения деревьев

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

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

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