跳转至

最大團搜索算法

前置知識：團

引入

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

團的問題在現實生活中也有體現。例如我們考慮一個社交網絡，其中圖的點代表用户，圖的邊代表其所連接的兩個用户互相認識。那麼我們找到了一個團，也就找到了一羣互相認識的人。

我們如果想要找到這個社交網絡中最大的一羣互相認識的人，那麼就需要用到最大團搜索算法。

我們已經介紹了 極大團 的概念，最大團指的是點數量最多的極大團。

解釋

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

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

過程

Bron–Kerbosch 算法對於這種想法進行了優化實現。它的基礎形式是通過給定三個集合：\(R\)、\(P\)、\(X\) 來遞歸地進行搜索。步驟如下：

  1. 初始化集合 \(R,X\) 分別為空，集合 \(P\) 是圖中所有點的集合。
  2. 每次從集合 \(P\) 中取頂點 \(v\)，當集合中沒有頂點時，有兩種情況：
    1. 集合 \(R\) 是最大團，此時集合 \(X\) 為空
    2. 無最大團，此時回溯
  3. 對於每一個從集合 \(P\) 中取得的頂點 \(v\)，有如下處理：
    1. 將頂點 \(v\) 加到集合 \(R\) 中，之後遞歸集合 \(R,P,X\)
    2. 從集合 \(P\) 中刪除頂點 \(v\)，並將頂點 \(v\) 添加到集合 \(X\) 中
    3. 若集合 \(P,X\) 都為空，則集合 \(R\) 即為最大團

此方法也可繼續優化。為了節省時間讓算法更快的回溯，可以通過設定關鍵點（pivot vertex）來進行搜索。另一種優化思路是在開始時把所有點排序，枚舉時按照下標順序，防止重複。

實現

偽代碼

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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++ 實現

實現代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#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;
}

例題

POJ 2989: All Friends

題目大意：給出 \(n\) 個人，其中有 \(m\) 對朋友，求最大團數量。

思路：模版題，要用 Bron–Kerbosch 算法

偽代碼：

1
2
3
4
5
6
7
8
 BronKerbosch(All, Some, None):  
     if Some and None are both empty:  
         report All as a maximal clique // 所有點已選完，且沒有不能選的點，累加答案  
     for each vertex v in Some: // 枚舉 Some 中的每一個元素  
         BronKerbosch1(All ⋃ {v}, Some ⋂ N(v), None ⋂ N(v))   
         // 將 v 加入 All，顯然只有與 v 為朋友的人才能作為備選，None 中也只有與 v 為朋友的才會對接下來造成影響  
         Some := Some - {v} // 已經搜過，從 Some 中刪除，加入 None  
         None := None ⋃ {v}

為了節省時間和讓算法更快的回溯，我們可以通過設定關鍵點（pivot vertex）\(v\) 進行優化。

我們知道在上述的算法中必然有許多重複計算之前計算過的極大團，然後回溯的過程。

以前文提到的 \(R\)、\(P\)、\(X\) 三個集合為例：

我們考慮如下問題，取集合 \(P\cup X\) 中的一個點 \(u\)，要與 \(R\) 集合構成極大團，那麼取的點必然是 \(P\cap N(u)\) 中一個點（\(N(u)\) 代表與 \(u\) 相鄰的點）。

如果取完 \(u\) 之後我們再取與 \(u\) 相鄰的點 \(v\) 也能加入到極大團，那麼我們只取 \(u\) 就好了。這樣做可以減少之後對 \(v\) 的重複計算。我們之後只需要取與 \(u\) 不相鄰的點。

加入優化後的 C++ 代碼實現：

實現代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <cstdio>
#include <cstring>
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; i <= m; ++i) {
      int u, v;
      scanf("%d %d", &u, &v);
      mp[u][v] = mp[v][u] = 1;
    }
    int tmp = work();
    if (tmp > 1000)
      puts("Too many maximal sets of friends.");
    else
      printf("%d\n", tmp);
  }
  return 0;
}

習題

參考資料

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Persdre
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用