- Алгоритм Брона — Кербоша
-
Алгоритм Брона — Кербоша
Алгоритм Брона — Кербоша — метод ветвей и границ для поиска всех клик (а также максимальных по включению независимых множеств вершин) неориентированного графа. Разработан голландскими математиками Броном и Кербошем в 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 и се: Первые nе элементов — это элементы множества 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 множество с большим числом вершин.
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; }
Сложность алгоритма
Линейна относительно количества клик в графе, а точнее O(nmμ), где
- 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
Wikimedia Foundation. 2010.