Реализации алгоритмов/Алгоритм Брона — Кербоша
Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа.
Вариации[править]
Нахождение максимальных (по включению) независимых множеств вершин[править]
Нетрудно видеть, что задача о клике и задача о независимом множестве по сути эквивалентны: каждая из них получается из другой, путем построения дополнения графа — такого графа, в котором есть все вершины исходного графа, причем в дополнении графа вершины соединены ребром тогда и только тогда, если они не были соединены в исходном графе.
Поэтому алгоритм Брона — Кербоша можно использовать для нахождения максимальных по включению независимых множеств вершин, если построить дополнение к исходному графу, либо изменив условие в основном цикле (условие остановки) и формирование новых множеств new_candidates и new_not:
- Условие в основном цикле: not не должно содержать ни одной вершины, НЕ СОЕДИНЕННОЙ НИ С ОДНОЙ из вершин во множестве candidates
- Для формирования new_candidates и new_not, необходимо удалять из candidates и not вершины, СОЕДИНЕННЫЕ с выбранной вершиной.
Реализация данной вариации алгоритма на языке Python:
def bron_kerbosch_max_by_inclusion(m):
results = []
def check(candidates, wrong):
for i in wrong:
q = True
for j in candidates:
if m[i][j]:
q = False
break
if q: return False
return True
def extend(compsub, candidates, wrong):
while candidates and check(candidates, wrong):
v = candidates[0]
compsub.append(v)
new_candidates = [ i for i in candidates if not m[i][v] and i != v ]
new_wrong = [ i for i in wrong if not m[i][v] and i != v ]
if not new_candidates and not new_wrong:
results.append(list(compsub))
else:
extend(compsub, new_candidates, new_wrong)
candidates.remove(v)
compsub.remove(v)
wrong.append(v)
extend([], list(range(len(m))), [])
return results
Нахождение максимальной клики / независимого множества максимального размера (МНМ)[править]
Для того, чтобы алгоритм искал максимальную по размеру клику/МНМ, необходимо:
- завести еще одно множество max_comsub (начальное значение — пустое множество)
- на шаге 4, когда найдена очередная клика/МНМ, сравнить размер (количество вершин) в comsub и в max_comsub и поместить в max_comsub множество с большим числом вершин.
Реализация на C++ с использованием стека.
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;
}