Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 07.11.2020, 22:20   #1
Artemii21
Пользователь
 
Регистрация: 04.04.2020
Сообщений: 26
Вопрос си++, алгоритм Брона и Кербоша

Приветствую, необходима помощь в объяснении алгоритма Брона и Кербоша для нахождения максимальных независимы множеств графа. Везде вижу примерно такой код, но объяснение достаточно неясное. Буду очень благодарен. Если не сложно, то было бы идеально пройтись по каждой строчке.

Код:
  {
            list <set<int> > kerbosh(int **&a, int SIZE)
     {
                set <int> M, G, K, P;
                list <set<int> > REZULT;
                for (int i = 0; i < SIZE; i++)
                {
                    K.insert(i);
                }
                int v, Count = 0, cnt = 0;
                int Stack1[100];
                set<int> Stack2[100];
                set<int>::iterator theIterator;
                theIterator = K.begin();
                while ((K.size() != 0) || (M.size() != 0))
                {
                    if (K.size() != 0)
                    {
                        theIterator = K.begin();
                        v = *theIterator;
                        Stack2[++Count] = M;
                        Stack2[++Count] = K;
                        Stack2[++Count] = P;
                        Stack1[++cnt] = v;
                        M.insert(v);
                        for (int i = 0; i < SIZE; i++)
                        {
                            if (a[v][i])
                            {
                                theIterator = K.find(i);
                                if (theIterator != K.end())
                                {
                                    K.erase(theIterator);
                                }
                                theIterator = P.find(i);
                                if (theIterator != P.end())
                                {
                                    P.erase(theIterator);
                                }
                            }
                        }
                        theIterator = K.find(v);
                        if (theIterator != K.end())
                        {
                            K.erase(theIterator);
                        }
                    }
                    else
                    {
                        if (P.size() == 0)
                        {
                            REZULT.push_back(M);
                        }
                        v = Stack1[cnt--];
                        P = Stack2[Count--];
                        K = Stack2[Count--];
                        M = Stack2[Count--];
                        theIterator = K.find(v);
                        if (theIterator != K.end())
                        {
                            K.erase(theIterator);
                        }
                        P.insert(v);
                    }
                }
                return  REZULT;
            }
        };
Artemii21 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм Брона-Кербоша или Java перевести на Си... VAAKAraceGUM Общие вопросы C/C++ 1 05.05.2012 01:09
Разветвляющийся алгоритм,циклический алгоритм и Многомерные массивы (Pascal) TrapperPTZ Помощь студентам 1 26.01.2012 08:58
Разработайте алгоритм методом пошаговой детализации и программу, реализующую этот алгоритм. iamhated Помощь студентам 1 15.01.2012 16:24
Разработайте алгоритм методом пошаговой детализации и программу, реализующую этот алгоритм iamhated Помощь студентам 1 14.01.2012 16:22
Алгоритм TMDS (Алгоритм передачи данных интерфейса DVI) Pro4RE Помощь студентам 2 24.04.2011 21:55