VPF::Раскраска графа - Форум программистов

afanp

Дата 17.12.2009, 17:54 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет

Собираюсь раскрасить граф, прибегнув к алгоритму Брона - Кербоша :
1) Выделяем максимально независимое множество вершина графа S
2) Раскрашиваем это подмножество в цвет 1
3) Возвращаемся к шагу 1 и выполняем операции для G/S
Кто может поделиться информацией о алгоритме Брона - Кербоша ? Помимо Кристофидиса не нашёл ничего

afanp

Дата 18.12.2009, 07:59 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 147
Регистрация: 25.11.2008

Репутация: нет
Всего: нет

Код


 private void BronKebroshStep(List<int> UsedSet, List<int> NotUsedSet, List<int> IndependentSet)
        {
            while (NotUsedSet.Count != 0 || IndependentSet.Count != 0)
            {
                List<int> NewNotUsedSet = new List<int>(NotUsedSet);
                List<int> NewUsedSet = new List<int>(UsedSet);
                if (NotUsedSet.Count != 0)
                {
                    int peak = NotUsedSet.First();
                    Push(NewNotUsedSet, NewUsedSet, peak, IndependentSet);
                    BronKebroshStep(NewUsedSet, NewNotUsedSet, IndependentSet);
                }
                else
                {
                    if (UsedSet.Count == 0) { print(IndependentSet); }
                    int v = IndependentSet.Last();
                    IndependentSet.Remove(v);
                    UsedSet.Add(v);
                    NotUsedSet.Remove(v);
                }
            }        
        }
Вот сам код, не получается правильно построить рекурсию :(

Возникают вопросы именно в описании алгоритма, не все до конца получается. Буду рад любой помощи

Это сообщение отредактировал(а) afanp - 18.12.2009, 14:11

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »