Dotcpp  >  编程教程  >  图论  >  简述最大团搜索算法

简述最大团搜索算法

点击打开在线编译器,边学边练

一、引入

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

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

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


二、解释

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

采用回溯策略的原因是,我们并不知道某个顶点 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;
  }



知识点标签:图论


本文固定URL:https://www.dotcpp.com/course/1073

算法竞赛教程
第一章 算法基础
第二章 搜索算法
第三章 排序算法
第四章 字符串相关
第五章 数学相关
第六章 动态规划
第七章 数据结构
第八章 图论
第九章 计算几何
第十章 其他算法
Dotcpp在线编译      (登录可减少运行等待时间)