極大團(tuán)(maximal clique)算法:Bron-Kerbosch算法

不了解極大團(tuán)(maximal clique)的瞎访，請(qǐng)看極大團(tuán)這篇文章。
該算法是由Coen Bron和Joep Kerbosch在1973提出的，論文原文
參考資料：
Bron-Kerbosch算法視頻介紹
 極大團(tuán)算法
當(dāng)給出一個(gè)圖之后葫督，我們應(yīng)該怎么去找出其中的極大團(tuán)呢？

圖

尋找極大團(tuán)的簡單思想就是：
1恋沃、生成原始圖的所有子圖(可能有2^n-1個(gè)子圖，n表示結(jié)點(diǎn)個(gè)數(shù))必指；
2囊咏、判斷這些子圖是不是團(tuán)；
3塔橡、將不是極大團(tuán)的團(tuán)都刪除梅割；
在我們上面給出的圖中，會(huì)有許多的子圖葛家，例如：

子圖

這里沒有列出所有的子圖户辞，只有部分。
在這些子圖里面癞谒，我們會(huì)發(fā)現(xiàn)有些并不是團(tuán)底燎，例如{1、2弹砚、3}組成的圖双仍，因?yàn)?和3之間并不相連，所以這樣的圖不符合要求桌吃，將其去掉朱沃。

團(tuán)

剩下的所有子圖，都是滿足了團(tuán)的要求的圖。最后逗物，其中還有許多搬卒，不是極大團(tuán)的，例如{0翎卓、1}就不是極大團(tuán)契邀，因?yàn)橛衶0、1莲祸、2}的存在蹂安。這些不是極大團(tuán)的團(tuán)，我們也要去掉锐帜。

極大團(tuán)

現(xiàn)在剩下的就是我們要找的極大團(tuán)。

Bron-Kerbosch算法(Version 1)

這個(gè)算法主要是構(gòu)造了三個(gè)集合畜号，我們假設(shè)：
R集合記錄的是當(dāng)前極大團(tuán)中已經(jīng)加入的點(diǎn)缴阎。
P集合記錄的是可能還能加入的點(diǎn)（也就是與R集合中所有點(diǎn)都有邊存在的點(diǎn)，這樣加入后简软，才會(huì)構(gòu)成團(tuán)）
X集合記錄的是已經(jīng)加入過某個(gè)極大團(tuán)的點(diǎn)（作用是判重蛮拔，因?yàn)闀?huì)從每個(gè)結(jié)點(diǎn)開始，枚舉所有的團(tuán)痹升，如果不對(duì)已經(jīng)加入某個(gè)極大團(tuán)的點(diǎn)建炫，進(jìn)行標(biāo)記，可能會(huì)有重復(fù)的極大團(tuán)出現(xiàn)）
偽代碼如下：

Bron-Kerbosch Algorithm(Version 1)
R={}   //已確定的極大團(tuán)頂點(diǎn)的集合
P={v}  //未處理頂點(diǎn)集疼蛾，初始狀態(tài)是所有結(jié)點(diǎn)
X={}   //已搜過的并且屬于某個(gè)極大團(tuán)的頂點(diǎn)集合

BronKerbosch(R, P, X):
   if P and X are both empty:
       report R as a maximal clique
   for each vertex v in P:
       BronKerbosch1(R ? {v}, P ? N(v), X ? N(v))
       P := P \ {v}
       X := X ? {v}

基礎(chǔ)的Born_Kerbosch算法：
1肛跌、對(duì)于每一個(gè)在集合P中的點(diǎn)v，我們把v加入集合R（集合P中的點(diǎn)與集合R中所有的點(diǎn)都是連接的察郁，這樣加入v衍慎，保證集合R依然是一個(gè)團(tuán)），對(duì)在P集合中且與點(diǎn)v相連的這部分集合中尋找下一個(gè)可能加入R集合的點(diǎn)（意思就是更新P集合皮钠，使P集合中的點(diǎn)依舊可以和R集合中的點(diǎn)相連接稳捆，因?yàn)檫@里新R集合新加入了v，所以只要是原P集合中且與v相連的麦轰，那這些結(jié)點(diǎn)就是與新的R集合中所有結(jié)點(diǎn)都相連）乔夯。
2、回溯時(shí)我們把v從P集合中移出款侵，加入X集合代表當(dāng)前狀態(tài)下對(duì)包含點(diǎn)v的極大團(tuán)已經(jīng)計(jì)算完畢了末荐。
3、R集合為極大團(tuán)的時(shí)候喳坠，必須要滿足P與X都是空的鞠评。P存放的是還可能加入R集合的點(diǎn)，P集合為空代表沒有點(diǎn)還能再加入到R集合當(dāng)中壕鹉，而X集合存放的是已經(jīng)完成極大團(tuán)計(jì)數(shù)的點(diǎn)剃幌，而且X集合中的點(diǎn)必然是與所有R集合中的點(diǎn)都有邊存在的(因?yàn)槲覀兠看蜗蛳逻M(jìn)行dfs的時(shí)候聋涨，還對(duì)P集合和X集合分別進(jìn)行取與R集合內(nèi)都相鄰的操作來保證，而且加入X集合中的點(diǎn)负乡，就是從R集合中取出來的牍白，當(dāng)然會(huì)和R集合中的所有結(jié)點(diǎn)都有邊)，也即X集合中點(diǎn)必然可以與R集合構(gòu)成極大團(tuán)抖棘。如果X集合不是空的的話茂腥，可以把X集合中的點(diǎn)加入R集團(tuán)，此時(shí)R集團(tuán)依然是團(tuán)切省，結(jié)點(diǎn)數(shù)比剛才增加了最岗，說明剛才的R集合就不是極大團(tuán)，那么說明R集合中的極大團(tuán)是在之前計(jì)算包含X集合中的點(diǎn)的極大團(tuán)的時(shí)候已經(jīng)計(jì)算過了的朝捆，故當(dāng)且僅當(dāng)P般渡、X都為空集合的時(shí)候R才是一個(gè)極大團(tuán)。

算法的實(shí)例：