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

Алгоритм Брона-Кербоша

20.09.2016, 10:59. Показов 3915. Ответов 0
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Здравствуйте, прошу вашей помощи в объяснении алгоритма Брона-Кэрбоша для нахождения максимальных независимых множеств графа, я нашел алгоритм на С++, но разобрать его не могу. Вот код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
    {
            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;
            }
        };
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
20.09.2016, 10:59
Ответы с готовыми решениями:

Алгоритм Брона-Кербоша или поиск клик в графе
Собственно озадачился решением одной задачи: имеется матрица весов взвешенного ориентированного...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки )
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар)
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная...

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм 1. Объясни, что...

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

Разработать алгоритм методом пошаговой детализации и программу, реализующую этот алгоритм
Расставить строки данной матрицы в порядке возрастания наибольших элементов в строках.

Построить алгоритм Маркова, который ищет НОД (Алгоритм Евклида)
Здравствуйте, ребята, выручайте. Весь инет перерыл, всю голову сломал, но не могу сделать. Суть в...

Алгоритм устранения непродуктивных нетерминалов, алгоритм построения недостижимых символов
Задание: найдите лишние нетерминалы в следующей грамматике с начальным нетерминалом S и в...

Построить алгоритм ДО и алгоритм ПОКА для вычислений значения функции на отрезке [a,b] с шагом h.
Построить алгоритм ДО и алгоритм ПОКА для вычислений значения функции на отрезке с шагом h....


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

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

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