Menu
Article Graph

最大团Bron–Kerbosch算法入门

NodeKey

NodeKey

• 3 min read

听了Yasola瞎逼逼打算去搞一下那些很混乱的东西。
首先就是这个最大团问题

建议先点开看看上面的百度百科链接。虽然东西很多，我也只是浏览了一下

瞎逼逼与个人理解

首先必须强调的是最大团是一个NP-Hard问题，目前并没有一个合适的在多项式时间内完美求得正解的算法。

而Bron–Kerbosch算法，名字好像是非常吊，其实就是各种优化过的搜索算法。
学习博客点这里

简单说一下个人理解。

Bron–Kerbosch算法基于基本搜索，但优化之处很多，优化有如下

  1. 比较常见的指定顺序搜索，避免重复
  2. 对于当前深度 dep , 如果剩余点数与之相加都不能更新 ans ，就剪枝
  3. dp 优化，用dp记录之前搜索得到的最大团数量，如无法更新ans，剪枝。

下面有两个入门 板子 题

HDU 1530 Maximum Clique

题意：
最大团的裸题。给你邻接矩阵，让你求最大团的点数。

思路：
套一套模板就行啦……

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
//#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 55;

int n, ans;
int g[maxn][maxn], dp[maxn];
int vex[maxn];

bool isClique(const int& sz, const int& end)
{
    range(i, 1, sz) if (!g[vex[i]][end]) return false;
    return true;
}

void dfs(int dep, int cur)
{
    if (dep + n - cur + 1 <= ans || dep + dp[cur] <= ans)
        return;
    range(i, cur, n) if (isClique(dep, i))
    {
        vex[dep + 1] = i;
        dfs(dep + 1, i + 1);
    }
    ans = max(dep, ans);
}

int main()
{
    while (~scanf("%d", &n) && n) {
        range(i, 1, n) range(j, 1, n) scanf("%d", &g[i][j]);
        fill(dp, dp + n + 1, 0), dp[n] = 1, ans = 0;
        rrange(i, 1, n - 1)
        {
            vex[1] = i;
            dfs(1, i + 1);
            dp[i] = ans;
        }
        printf("%d\n", dp[1]);
    }
    return 0;
}

POJ 1419 Graph Coloring

题意：
给你一些边，让你求最大独立集。

思路：
无向图的最大独立集 = 补图的最大团。
因此建立补图，跑一遍即可。

AC Code

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int maxn = 105;

int n, m, ans;
int g[maxn][maxn], dp[maxn];
int vex[maxn], avex[maxn];

bool isClique(const int& sz, const int& end)
{
    range(i, 1, sz) if (!g[vex[i]][end]) return false;
    return true;
}

void dfs(int dep, int cur)
{
    if (dep + n - cur + 1 <= ans || dep + dp[cur] <= ans)
        return;
    range(i, cur, n) if (isClique(dep, i))
    {
        vex[dep + 1] = i;
        dfs(dep + 1, i + 1);
    }
    if (ans < dep) {
        ans = dep;
        memcpy(avex, vex, sizeof vex);
    }
}

int main()
{
    int T, u, v;
    scanf("%d", &T);
    while (T--) {
        scanf("%d %d", &n, &m);
        range(i, 1, n) range(j, 1, n) g[i][j] = 1;
        while (m--) {
            scanf("%d %d", &u, &v);
            g[u][v] = g[v][u] = 0;
        }
        fill(dp, 0), dp[n] = 1, ans = 0;
        rrange(i, 1, n - 1)
        {
            vex[1] = i;
            dfs(1, i + 1);
            dp[i] = ans;
        }
        printf("%d\n", dp[1]);
        range(i, 1, ans) printf("%d%c", avex[i], " \n"[i == ans]);
    }
    return 0;
}
Share