首页 > 搜索 > bronkerbosch算法,bron kerbosch 算法

bronkerbosch算法,bron kerbosch 算法

互联网 2020-10-19 23:05:49
在线算命,八字测算命理

描述:团就是最大完全子图。(极大团)

给定无向图G=(V,E)。如果U包含于V,且对任意u,v属于U且有(u,v)属于E,则称U是G的完全子图。

G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中,即U就是最大完全子图。

G的最大团是指G中所含顶点数最多的团。

 

// 最大团: V中取K个顶点,两点间相互连接

// 最大独立集: V中取K个顶点,两点间不连接 

// 最大团数量: 补图中最大独立集数

 

问题:

1. POJ-2989 求一个无向图的极大团的个数。

2. ZOJ-1492 求一个无向图的最大团数。

 

求解最大团、极大团这里用到了Bron–Kerbosch算法,在网上搜集了大佬们两种不同的写法。

两种复杂度都为O(3^n),推荐:求最大团用后者,求极大团用前者。

 

这个算法主要是构造了三个集合,我们假设:

R集合记录的是当前极大团中已经加入的点。

P集合记录的是可能还能加入的点(也就是说可能与R集合中所有点都有边存在的点)。

X集合记录的是已经完成极大团计数的点(作用是判重)

P∪X是所有可能与R集合构成极大团的点集(虽然我们已经知道X中的点不可能再参与极大团的构成),也就是与最后一个加入R集合相连的点相连的点的一部分。

基础的Born_Kerbosch算法,对于每一个点P中的点v我们把v加入集合R,对在P集合中且与点v相连的这部分集合中寻找下一个可能加入R集合的点,回溯时我们把v从P集合中移出,加入X集合代表当前状态下对包含点v的极大团已经计算完毕了。R集合为极大团的时候,必须要满足P与X都是空的,P存放的是还可能加入R集合的点,P集合为空代表没有点还能再加入到R集合当中,而X集合存放的是已经完成极大团计数的点,而且X集合中的点必然是与所有R集合中的点都有边存在的(因为我们每次向下进行dfs的时候,还对P集合和X集合分别进行取与R集合内都相邻的操作来保证),也即X集合中点必然可以与R集合构成极大团,如果X集合不是空的的话,那么说明R集合中的极大团是在之前计算包含X集合中的点的极大团的时候已经计算过了的,故当且仅当P、X都为空集合的时候R才是一个极大团。

 

代码中我们假设all为已确定的极大团顶点的集合,some为未处理顶点集(初始状态是全部顶点),none为不取的(已搜过的)顶点集。

最朴素的dfs如下:

 

int some[maxn][maxn];int none[maxn][maxn];int all[maxn][maxn];int mp[maxn][manx];void dfs(int d, int an, int sn, int nn){if(!sn && !nn) return;for(int i = 0; i < sn; ++i){int v = some[d][i];for(int j = 0; j < an; ++j)all[d+1][j] = all[d][j];all[d+1][an] = v;int tsn = 0, tnn = 0;for(int j = 0; j < sn; ++j)if(mp[v][some[d][j]])some[d+1][tsn++] = some[d][j];for(int j = 0; j < nn; ++j)if(mp[v][none[d][j]])none[d+1][tnn++] = none[d][j];dfs(d+1, an+1, tsn, tnn);some[d][i] = 0, none[d][nn++] = v;}}

 

 

为了节省时间和让算法更快的回溯,我们可以通过设定关键点pivot vertex u进行优化。

我们知道在上述的算法中必然有许多重复计算之前计算过的极大团然后回溯的过程。我们考虑如下问题,取集合P∪X中的一个点u,要与R集合构成极大团,那么取的点必然是P∩N(u)中一个点(N(u)代表与u相邻的点)。通俗的讲就是如果取完u之后我们再取与u相邻的点v也能加入到极大团,那么我们只取u就好了,从而剪掉了之后对v的白用功,所以再要么就是取与u不相邻的点,这样我们照样可以重复不漏的计算所有极大团,从而减少许多不必要的计算。而我们要想进一步减少计算,我们就可以取邻居尽可能多的u,即使我们要遍历的点尽可能减少,但是其实没必要写,寻找合适的u也会减少一定的效率。

 

加入优化后代码1(POJ-2989为例 47ms):

 

#include #include using namespace std;const int maxn = 130;bool mp[maxn][maxn];int some[maxn][maxn], none[maxn][maxn], all[maxn][maxn];int n, m, ans;void dfs(int d, int an, int sn, int nn){if(!sn && !nn) ++ans;int u = some[d][0];for(int i = 0; i < sn; ++i){int v = some[d][i];if(mp[u][v]) continue;for(int j = 0; j < an; ++j)all[d+1][j] = all[d][j];all[d+1][an] = v;int tsn = 0, tnn = 0;for(int j = 0; j < sn; ++j)if(mp[v][some[d][j]])some[d+1][tsn++] = some[d][j];for(int j = 0; j < nn; ++j)if(mp[v][none[d][j]])none[d+1][tnn++] = none[d][j];dfs(d+1, an+1, tsn, tnn);some[d][i] = 0, none[d][nn++] = v;if(ans > 1000) return;}}int work(){ans = 0;for(int i = 0; i < n; ++i) some[1][i] = i+1;dfs(1, 0, n, 0);return ans;}int main(){while(~scanf("%d %d", &n, &m)){memset(mp, 0, sizeof mp);for(int i = 1; i1000) puts("Too many maximal sets of friends.");else printf("%d\n", tmp);}return 0;}

 

 

加入优化后代码2(ZOJ-1492为例 330ms):

 

#include #include #include using namespace std;const int maxn = 130;bool mp[maxn][maxn];int some[maxn][maxn], none[maxn][maxn], all[maxn][maxn];int n, m, ans;void dfs(int d, int an, int sn, int nn){if(!sn && !nn) ans = max(ans, an);int u = some[d][0];for(int i = 0; i < sn; ++i){int v = some[d][i];if(mp[u][v]) continue;for(int j = 0; j < an; ++j)all[d+1][j] = all[d][j];all[d+1][an] = v;int tsn = 0, tnn = 0;for(int j = 0; j < sn; ++j)if(mp[v][some[d][j]])some[d+1][tsn++] = some[d][j];for(int j = 0; j < nn; ++j)if(mp[v][none[d][j]])none[d+1][tnn++] = none[d][j];dfs(d+1, an+1, tsn, tnn);some[d][i] = 0, none[d][nn++] = v;}}int work(){ans = 0;for(int i = 0; i < n; ++i) some[1][i] = i+1;dfs(1, 0, n, 0);return ans;}int main(){while(~scanf("%d", &n) && n){for(int i = 1; i
免责声明:非本网注明原创的信息,皆为程序自动获取互联网,目的在于传递更多信息,并不代表本网赞同其观点和对其真实性负责;如此页面有侵犯到您的权益,请给站长发送邮件,并提供相关证明(版权证明、身份证正反面、侵权链接),站长将在收到邮件12小时内删除。

相关阅读

一周热门

查看更多