最大团问题——Bron-Kerbosch算法

Author Avatar
Mogician_Jeff Apr 12, 2018

@(图)[最大团]

最大团问题——Bron-Kerbosch算法

给定无向图G=(V,E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果U V，且对任意两个顶点u，v∈U有(u,v)∈E，则称U是G的完全子图。G的完全子图U是G的团。G的最大团是指G的最大完全子图。
如果UÍV且对任意u，v∈U有(u,v)不属于E，则称U是G的空子图。G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。G的最大独立集是G中所含顶点数最多的独立集。
对于任一无向图G=(V,E)，其补图G’=(V’,E’)定义为：V’=V，且(u,v)∈E’当且仅当(u,v)∉E。
如果U是G的完全子图，则它也是G’的空子图，反之亦然。因此，G的团与G’的独立集之间存在一一对应的关系。特殊地，U是G的最大团当且仅当U是G’的最大独立集。
通俗点讲就是在一个无向图中找出一个点数最多的完全图。

Bron-Kerbosch 算法

最大独立集： 顶点集V中取 K个顶点，其两两间无连接。

最大团：　顶点集V中取 K个顶点，其两两间有边连接。

最大团中顶点数量 = 补图的最大独立集中顶点数量　
　
就可以通过求其补图中最大团中顶点数量,就可得出原图中最大独立集中顶点数量了.

Bron-Kerbosch算法一般有两种形式，一种是线性枚举的dfs，一种是基于集合操作的dfs
其中，推荐前一种方法用来找最大团，因为效率非常高
第二种方法则可以用来找极大团，或者统计极大团的数量

对于求解 最大团中顶点数量 的搜索过程中用到的剪枝,如下

  1. 剪枝1：常用的指定顺序, 即枚举第i个顶后, 以后再枚举时枝考虑下标比大它的, 避免重复。
  2. 剪枝2：自己开始从前往后的枚举顶点, TLE两次. 后来从后往前枚举顶点，发现可以利用顶点之间的承袭性.我用num[i] 记录的可选顶点集合为 V[i, i+1, … , n] 中的最大团数目， 目标是求num[1].
    分析易知, num[i] = num[i+1] 或者 num[i]+1 (num[1…n] 具有非降的单调性,从后往前求)
    由这个式子以及num[]信息的记录，使得我们可以增加两处剪枝:
    3.上/下剪枝：假设当前枚举的是顶点x, 它的第一个邻接顶是i (标号一定比x大，即num[i]已经求出) 我们可以知道， 若 1 + num[i] <= best, 那么是没没要往下枚举这个顶点x了，因为包含它的团是不可能超过我们目前的最优值的。
  3. 立即返回剪枝: 由于num[i]最大可能为num[i+1]+1, 所以在枚举顶点i时，只要一更新best，可知此时的num[i]就为num[i+1]+1了，不需要再去尝试找其他的方案了，所以应立即返回.

例题

HDOJ1530
最大团裸题，采用Bron-Kerbosch算法。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int maxn = 60;
int best;  //记录最大团的值
int mat[maxn][maxn],num[maxn],n;  //num数组记录包含这个点的极大团值

bool dfs(int *adj,int tot,int cnt)
{
  int i,j,k;
  int t[maxn];  //t是下一层搜索待查找的点
  if(tot == 0)  //待查找的点不存在了
  {
    if(cnt > best)   //如果团内点的数目大于当前记录的最大团的点的数目，更新best
    {
      best = cnt;
      return true;
    }
    return false;
  }
  for(i=0;i<tot;i++)
  {
    if(cnt + (tot - i) <= best) return false;  //剪枝1:如果当前团内点数cnt与待搜索的点数tot-i之和小于当前最大团点数best，则返回
    if(cnt + num[adj[i]] <= best) return false;  //剪枝2:如果当前团内点数与包含i的团点数之和小于最大团点数best，则返回
    for(k=0,j=i+1;j<tot;j++)  //k记录了下一层待搜索的点的数量
      if(mat[adj[i]][adj[j]]) t[k++] = adj[j];  //遍历待查找的点中比点i大的，若它们之间存在边，则加入到t数组中
    if(dfs(t,k,cnt+1))  return true;
  }
  return false;
}

int max_clique()
{
  int i,j,k;
  int adj[maxn];
  if(n <= 0)  return 0; //一个点都没有
  best = 0; //初始化最大团数量
  for(i=n-1;i>=0;i--)
  {
    for(k=0,j=i+1;j<n;j++)  // 遍历 [i+1, n] 间顶点
      if(mat[i][j]) adj[k++] = j;
    dfs(adj,k,1);
    num[i] = best; //更新best
  }
  return best;
}

int main()
{
  while(cin >> n && n)
  {
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
      cin >> mat[i][j];
    cout << max_clique() << endl;
  }
}

例题2

POJ2989
这道题要求极大团的数量，显然这个时候第一种方法不适用。因为第一种方法只能找到最大团，并不能判断当前团是否为一个极大团。所以我们要用第二种方法来求。

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

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也会减少一定的效率。

也就是说，在取点的时候，对于一个点u，我们只需要计算点u和不与点u相邻的点就可以了

这里贴上POJ2989的优化算法

#include<iostream>
#include<cstring>
#include<vector>
#include<cstdio>
#include<string>
using namespace std;
const int maxn = 128 + 10;
const string STR = "Too many maximal sets of friends.";
int mp[maxn][maxn];
int all[maxn][maxn];
int some[maxn][maxn];
int none[maxn][maxn];
int n,m,ans;

void dfs(int d,int an,int sn,int nn)
{
  if(!sn && !nn)  ans++;  //如果P集合与X集合都为空，则找到了极大团
  int u = some[d][0];  //标记为特殊点
  for(int i=0;i<sn;i++)
  {
    int v = some[d][i];
    if(mp[u][v])  continue;  //如果v与u相邻，则剪枝
    for(int j=0;j<an;j++)
      all[d+1][j] = all[d][j];  //记录下一次搜索的all
    all[d+1][an] = v;  //将v加入all
    int tsn = 0,tnn = 0;  //记录下一次搜索的sn与nn
    for(int j=0;j<sn;j++)
    if(mp[v][some[d][j]]) some[d+1][tsn++] = some[d][j];  // P与N(v)取交集
    for(int j=0;j<nn;j++)
    if(mp[v][none[d][j]]) none[d+1][tnn++] = none[d][j];  // X与N(v)取交集
    dfs(d+1,an+1,tsn,tnn);
    some[d][i] = 0;  //回溯的时候把v从some中取出
    none[d][nn++] = v;  //回溯的时候往none中加入v节点
    if(ans > 1000)  return; //超过1000就满足条件了
  }
}

int solve()
{
  ans = 0;
  for(int i=0;i<n;i++)  some[1][i] = i + 1;
  dfs(1,0,n,0);
  return ans;
}

int main()
{
  int a,b;
  while(cin >> n >> m)
  {
    memset(mp,0,sizeof(mp));
    for(int i=0;i<m;i++)
    {
      cin >> a >> b;
      mp[a][b] = mp[b][a] = 1;
    }
    int result = solve();
    if(result > 1000) cout << STR << endl;
    else cout << result << endl;
  }
}
Powered by Hexo
Theme - Material
... ... ...