一、引入

在計算機科學(xué)中，團問題指的是在給定的圖中找到團（頂點的子集，都彼此相鄰，也稱為完全子圖）的計算問題。

團的問題在現(xiàn)實生活中也有體現(xiàn)。例如我們考慮一個社交網(wǎng)絡(luò)，其中圖的點代表用戶，圖的邊代表其所連接的兩個用戶互相認識。那么我們找到了一個團，也就找到了一群互相認識的人。

我們?nèi)绻胍业竭@個社交網(wǎng)絡(luò)中最大的一群互相認識的人，那么就需要用到最大團搜索算法，最大團指的是點數(shù)量最多的極大團。

二、解釋

想法是利用遞歸和回溯，用一個列表存儲點，每次加入點進來都檢查這些點是否仍在一個團中。如果加入進來這個點后就無法還是一個團了，就回溯到滿足條件的位置，重新加入別的點。

采用回溯策略的原因是，我們并不知道某個頂點 v 最終是否是最大團中的成員。如果遞歸算法選擇 v  作為最大團的成員時，并沒有找到最大團，那么應(yīng)該回溯，并查找最大團中沒有 v 的解。

三、過程

Bron-Kerbosch 算法對于這種想法進行了優(yōu)化實現(xiàn)。它的基礎(chǔ)形式是通過給定三個集合：R、P、X 來遞歸地進行搜索。步驟如下：

（1）初始化集合R，X分別為空，集合P是圖中所有點的集合。

（2）每次從集合P中取頂點 v，當(dāng)集合中沒有頂點時，有兩種情況：

a. 集合R是最大團，此時集合X為空；

b. 無最大團，此時回溯。

（3）對于每一個從集合P中取得的頂點 v，有如下處理：

a. 將頂點 v 加到集合R中，之后遞歸集合R，P，X；

b. 從集合P中刪除頂點 v，并將頂點 v 添加到集合X中；

c. 若集合P，X都為空，則集合R即為最大團。

此方法也可繼續(xù)優(yōu)化。為了節(jié)省時間讓算法更快的回溯，可以通過設(shè)定關(guān)鍵點（pivot vertex）來進行搜索。另一種優(yōu)化思路是在開始時把所有點排序，枚舉時按照下標(biāo)順序，防止重復(fù)。

偽代碼：

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++代碼實現(xiàn)：

  #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;
  }