|
Алгоритм Брона — КербошаАлгоритм Брона — Кербоша — метод гілок і меж для пошуку всіх клік (а також максимальних за включенням незалежних множин вершин) неорієнтованого графу. Розробили 1973 року голландські математики Бронній і Кербош. Досі це один із найефективніших алгоритмів пошуку клік. АлгоритмАлгоритм використовує той факт, що будь-яка кліка в графі є його максимальним за включенням повним підграфом. Починаючи з одиничної вершини (що утворює повний підграф), алгоритм на кожному кроці намагається збільшити вже побудований повний підграф, додаючи в нього вершини з множини кандидатів. Висока швидкість забезпечується відтинанням при переборі варіантів, які гарантовано не приведуть до побудови кліки, для чого використовується додаткова множина, в яку поміщаються вершини, які вже були використані для збільшення повного підграфу. Алгоритм оперує трьома множинами вершин графу:
Алгоритм є рекурсивною процедурою, що застосовується до цих трьох множинам. ПРОЦЕДУРА 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 Реалізація
С++ реалізація алгоритму (використовуючи масиви як стек) 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:
Знаходження максимальної кліки / незалежної множини максимального розміру (МНМ)Для того, щоб алгоритм шукав максимальну за розміром кліку / МНМ, необхідно:
С++ реалізація використовуючи стек 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;
}
Складність алгоритмуЛінійна відносно кількості клік в графі, де
Tomita, Tanaka і Haruhisa в 2006 показали, що в гіршому випадку алгоритм працює за O(3n/3). Див. такожЛітература
ПосиланняРеалізація алгоритму на Java [Архівовано 26 січня 2011 у Wayback Machine.] |