Алгоритм Брона — Кербоша — метод гілок і меж для пошуку всіх клік (а також максимальних за включенням незалежних множин вершин) неорієнтованого графу. Розробили 1973 року голландські математики Бронній і Кербош. Досі це один із найефективніших алгоритмів пошуку клік.
Алгоритм
Алгоритм використовує той факт, що будь-яка кліка в графі є його максимальним за включенням повним підграфом. Починаючи з одиничної вершини (що утворює повний підграф), алгоритм на кожному кроці намагається збільшити вже побудований повний підграф, додаючи в нього вершини з множини кандидатів. Висока швидкість забезпечується відтинанням при переборі варіантів, які гарантовано не приведуть до побудови кліки, для чого використовується додаткова множина, в яку поміщаються вершини, які вже були використані для збільшення повного підграфу.
Алгоритм оперує трьома множинами вершин графу:
Множина compsub — множина, що містить на кожному кроці рекурсії повний підграф для даного кроку. Будується рекурсивно. Множина candidates — множина вершин, які можуть збільшити compsub Множина not — множина вершин, які вже використовувалися для розширення compsub на попередніх кроках алгоритму.
Алгоритм є рекурсивною процедурою, що застосовується до цих трьох множинам.
ПРОЦЕДУРА extend(candidates, not): ПОКИ candidates НЕ порожньо І not НЕ містить вершини, з'єднаної з усіма вершинами з candidates, ВИКОНУВАТИ: 1 Вибираємо вершину v з candidates і додаємо її в compsub 2 Формуємо new_candidates і new_not, видаляючи з candidates і not вершини, не З'ЄДНАНІ з v 3 ЯКЩО new_candidates і new_not порожні 4 ТО compsub - кліка 5 ІНАКШЕ рекурсивно викликаємо extend(new_candidates,new_not) 6 Видаляємо v з compsub і candidates і поміщаємо в not
Реалізація
Множина compsub використовується як стек, і може бути реалізована за допомогою глобального одновимірного масиву. Множини candidates і not можна зберігати в одновимірному масиві, використовуючи два індекси ne і се: Перші ne елементів — це елементи множини not, а наступні ce−ne елементів — множини candidates. При такій реалізації, можна використовувати наступні твердження для перевірки умов у рядках 1 та 4: * ne = ce: множина candidates порожня * ne = 0: множина not порожня * се = 0: обидві множини candidates і not порожні * Для переміщення елементу з candidates в not потрібно збільшити індекс ne (за умови, що як вершина-кандидат вибиралася перша вершина з candidates, або вибрана вершина була обміняна з першою) Алгоритм може бути досить легко реалізований без застосування рекурсії Для прискорення алгоритму можна використовувати евристики при виборі вершини-кандидата на кроці 1
С++ реалізація алгоритму (використовуючи масиви як стек)
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; std::set<int> Stack2; std::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;
Варіації
Знаходження максимальних (по включенню) незалежних множин вершин
Неважко побачити, що задача про кліку і задача про незалежні множини по суті еквівалентні: кожна з них виходить з іншої, шляхом побудови доповнення графу — такого графу, в якому є всі вершини вихідного графу, причому в доповненні графу вершини з'єднані ребром тоді і тільки тоді, якщо вони не були з'єднані у вихідному графі.
Тому алгоритм Брона — Кербоша можна використовувати для знаходження максимальних по включенню незалежних множин вершин, якщо побудувати доповнення до вихідного графу, або змінивши умову для основного циклу (умову завершення) та формування нових множин new_candidates і new_not: Умова в основному циклі: not не повинно містити жодної вершини, НЕ З'ЄДНАНОЇ З ЖОДНОЮ з вершин у множині candidates Для формування new_candidates і new_not, необхідно видаляти з candidates і not вершини, З'ЄДНАНІ з обраною вершиною.
Знаходження максимальної кліки / незалежної множини максимального розміру (МНМ) Для того, щоб алгоритм шукав максимальну за розміром кліку / МНМ, необхідно: Завести ще одну множину max_comsub(початкове значення — порожня множина) У кроці 4, коли знайдена чергова кліка / МНМ, порівняти розмір (кількість вершин) в comsubі в max_comsubі помістити в max_comsub множину з більшим числом вершин.
С++ реалізація використовуючи стек
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; std::set<int> Stack2; std::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;
Складність алгоритму
Лінійна відносно кількості клік в графі, де n — кількість вершин m — кількість ребер μ — кількість клік Tomita, Tanaka і Haruhisa в 2006 показали, що в гіршому випадку алгоритм працює за O(3n/3).
Див. також
Хроматичне число Перебір з поверненням Список алгоритмів Алгоритми на графах
Література
Bron C., Kerbosh J. (1973), Algorithm 457 — Finding all cliques of an undirected graph, Comm. of ACM, 16, p. 575—577 Etsuji Tomita, Akira Tanaka, Haruhisa Takahashi (2006), The worst-case time complexity for generating all maximal cliques and computational experiments, Theoretical Computer Science, Vol 363, Issue 1, , p. 28-42
Посилання
Реалізація алгоритму на Java Реалізація алгоритму на Python Реалізація алгоритму на C++11 з модульними тестами