简述最大团搜索算法

一、引入

在计算机科学中，团问题指的是在给定的图中找到团（顶点的子集，都彼此相邻，也称为完全子图）的计算问题。

团的问题在现实生活中也有体现。例如我们考虑一个社交网络，其中图的点代表用户，图的边代表其所连接的两个用户互相认识。那么我们找到了一个团，也就找到了一群互相认识的人。

我们如果想要找到这个社交网络中最大的一群互相认识的人，那么就需要用到最大团搜索算法，最大团指的是点数量最多的极大团。

二、解释

想法是利用递归和回溯，用一个列表存储点，每次加入点进来都检查这些点是否仍在一个团中。如果加入进来这个点后就无法还是一个团了，就回溯到满足条件的位置，重新加入别的点。

采用回溯策略的原因是，我们并不知道某个顶点 v 最终是否是最大团中的成员。如果递归算法选择 v  作为最大团的成员时，并没有找到最大团，那么应该回溯，并查找最大团中没有 v 的解。

三、过程

Bron-Kerbosch 算法对于这种想法进行了优化实现。它的基础形式是通过给定三个集合：R、P、X 来递归地进行搜索。步骤如下：

（1）初始化集合R，X分别为空，集合P是图中所有点的集合。

（2）每次从集合P中取顶点 v，当集合中没有顶点时，有两种情况：

a. 集合R是最大团，此时集合X为空；

b. 无最大团，此时回溯。

（3）对于每一个从集合P中取得的顶点 v，有如下处理：

a. 将顶点 v 加到集合R中，之后递归集合R，P，X；

b. 从集合P中删除顶点 v，并将顶点 v 添加到集合X中；

c. 若集合P，X都为空，则集合R即为最大团。

此方法也可继续优化。为了节省时间让算法更快的回溯，可以通过设定关键点（pivot vertex）来进行搜索。另一种优化思路是在开始时把所有点排序，枚举时按照下标顺序，防止重复。

伪代码：

R := {}
P := node set of G 
X := {}

BronKerbosch1(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}

C++代码实现：

  #include <algorithm>
  #include <cstdio>
  #include <cstring>
  #include <iostream>
  using namespace std;
  const int MAXN = 105;

  struct MaxClique {
    bool g[MAXN][MAXN];
    int n, dp[MAXN], st[MAXN][MAXN], ans;

    // dp[i]表示第i个点之后能组成的最大团的大小，
    // st[i][j]表示算法中第i层dfs所需要的点的集合，保存有可能是最大团其中之一的点

    void init(int n) {
      this->n = n;
      memset(g, false, sizeof(g));
    }

    void addedge(int u, int v, int w) { g[u][v] = w; }

    bool dfs(int sz, int num) {
      if (sz == 0) {
        if (num > ans) {
          ans = num;
          return true;
        }
        return false;
      }
      for (int i = 0; i < sz; i++) {  // 在第num层的集合中枚举一个点i
        if (sz - i + num <= ans) return false;  // 剪枝1
        int u = st[num][i];
        if (dp[u] + num <= ans) return false;  // 剪枝2
        int cnt = 0;
        for (
            int j = i + 1; j < sz;
            j++) {  // 在第num层遍历在i之后的且与i所相连的点，并且加入第num+1层集合
          if (g[u][st[num][j]]) st[num + 1][cnt++] = st[num][j];
        }
        if (dfs(cnt, num + 1)) return true;
      }
      return false;
    }

    int solver() {
      ans = 0;
      memset(dp, 0, sizeof(dp));
      for (int i = n; i >= 1; i--) {
        int cnt = 0;
        for (int j = i + 1; j <= n; j++) {  // 初始化第1层集合
          if (g[i][j]) st[1][cnt++] = j;
        }
        dfs(cnt, 1);
        dp[i] = ans;
      }
      return ans;
    }

  } maxclique;

  int main() {
    int n;
    while (scanf("%d", &n), n) {
      maxclique.init(n);
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
          int x;
          scanf("%d", &x);
          maxclique.addedge(i, j, x);
        }
      }
      printf("%d\n", maxclique.solver());
    }
    return 0;
  }