Алгоритм Брона — Кербоша
Алгоритм Брона — Кербоша — метод гілок і меж для пошуку всіх клік (а також максимальних за включенням незалежних множин вершин) неорієнтованого графу. Розробили 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[100];
std::set<int> Stack2[100];
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[100];
std::set<int> Stack2[100];
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, ISSN 0304-3975, p. 28-42
Посилання ред.
Реалізація алгоритму на Java [Архівовано 26 січня 2011 у Wayback Machine.]
Реалізація алгоритму на Python [Архівовано 29 жовтня 2013 у Wayback Machine.]
Реалізація алгоритму на C++11 з модульними тестами [Архівовано 12 лютого 2017 у Wayback Machine.]