Bron-Kerbosch算法

求一般图最大团

原理

其实就是递归暴力，伪代码如下：

R, P, X 是三个集合, 初始时 R, X 为空, P 是点集
设 N(v) 表示点 v 的邻接顶点集合
设 + 表示集合并, ^ 表示集合交, - 表示集合删除
Bron_Kerbosch(R, P, X)
{
    if (P == 空集 && X == 空集) return R;
    for (v : P)
    {
        Bron_Kerbosch(R + {v}, P ^ N(v), X ^ N(v))
        P = P - {v}
        X = X + {v}
	}
}

其实很好理解， $R$ 表示最大团， $X$ 用来判重， $P$ 表示还未考虑的点

代码

加了一些剪枝

int n, m;
bool G[N][N]; //存反图
int ans, group[N]; //答案
int cnt[N];
int p[N]; //记录选则
bool dfs(int x, int as)
{
	for (int i = x + 1; i <= n; ++i)
    {
        if (cnt[i] + as <= ans) return false;
        if (G[x][i])
        {
            for (int j = 1; j <= as; ++j) if (!G[i][p[j]]) goto E_O_F_i;
            p[as + 1] = i;
            if (dfs(i, as + 1)) return true;
        }
        E_O_F_i:;
	}
    if (as > ans)
    {
        std::copy(p + 1, p + as + 1, group + 1);
        return ans = as, true;
	}
    return false;
}
void maxClique()
{
    ans = -1;
    for (int i = n; i; --i)
    {
        p[1] = i;
        dfs(i, 1);
        cnt[i] = ans;
    }
}