最大团搜索算法

前置知识:

问题引入

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

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

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

我们已经介绍了 极大团 的概念,最大团指的是点数量最多的极大团。

算法介绍

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

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

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

  1. 初始化集合 分别为空,集合 是图中所有点的集合。
  2. 每次从集合 中取顶点 ,当集合中没有顶点时,有两种情况:
    1. 集合 是最大团,此时集合 为空
    2. 无最大团,此时回溯
  3. 对于每一个从集合 中取得的顶点 ,有如下处理:
    1. 将顶点 加到集合 中,之后递归集合
    2. 从集合 中删除顶点 ,并将顶点 添加到集合
    3. 若集合 都为空,则集合 即为最大团

此方法也可继续优化。为了节省时间让算法更快的回溯,可以通过设定关键点(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;
  }

例题

???+note "POJ 2989: All Friends 题目大意:给出 个人,其中有 对朋友,求最大团数量。

思路:模版题,要用 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) 进行优化。

我们知道在上述的算法中必然有许多重复计算之前计算过的极大团,然后回溯的过程。

以前文提到的 三个集合为例:

我们考虑如下问题,取集合 中的一个点 ,要与 集合构成极大团,那么取的点必然是 中一个点( 代表与 相邻的点)。

如果取完 之后我们再取与 相邻的点 也能加入到极大团,那么我们只取 就好了。这样做可以减少之后对 的重复计算。我们之后只需要取与 不相邻的点。

加入优化后的 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;
  }

习题

参考资料


评论