5 / 5 / 0
Регистрация: 25.11.2011
Сообщений: 56
1

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

12.04.2012, 21:45. Показов 1491. Ответов 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)
}

но ничего не пойму. Помогите плиз.
Буду благодарен за помощь.
__________________
Помощь в написании контрольных, курсовых и дипломных работ, диссертаций здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
12.04.2012, 21:45
Ответы с готовыми решениями:

Массив: Учащиеся участвовали в посадке деревьев. Сколько деревьев было посажено
1)Учащиеся 8-х классов участвовали в посадке деревьев. 8-а посадил 100 деревьев, 8-б —122 дерева,...

Алгоритм генерации графов и деревьев
Добрый день. Подскажите пожалуйста алгоритм генерирования графов и деревьев и как это реализовать в...

Алгоритм поиска всех деревьев в графе
Имеется граф. Необходимо найти множество всех деревьев. Где дерево это минимальная неизбыточная...

соотношение для деревьев
доказать с помощью индукции что для дерева с n вершинами и m ребрами выполняеться соотношение m=n-1

0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.04.2012, 21:45
Помогаю со студенческими работами здесь

Реализация функции Show для деревьев
Здравствуйте! Ошибка Ноу инстанс фор Show - на той строке, где объявляется функция instance Пока...

Разработать процедуры и функции для обработки бинарных деревьев
Розробити процедури та функції для обробки бінарних дерев: побудови бінарного дерева пошуку,...

C/C++ vs Objective-C для обхода больших деревьев - вопрос оптимизации
Добрый день! Появилась необходимость обрабатывать многотысячный словарь ("словарь" - буквально,...

Создать функции ввода/вывод для бинарных деревьев
Не могу создать функции ввода/вывод для бинаных деревьев. очень срочно нужно! скажите где ошибка......

Написать программу для проверки двух деревьев на изоморфность
Добавляю готовый код работающий в Prolog 5.2 "Написать программу для проверки двух деревьев на...

Доказать формулу для количества остовных деревьев в полном графе
Задача состоит в том, что бы доказать, что эта рекуррентная формула показывает колличество остовных...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru