极大团
介绍
描述：团就是最大完全子图。(极大团)
给定无向图G=(V,E)。如果U包含于V，且对任意u，v属于U且有(u，v)属于E，则称U是G的完全子图。
G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中，即U就是最大完全子图。
G的最大团是指G中所含顶点数最多的团。
最大团： V中取K个顶点，两点间相互连接
最大独立集： V中取K个顶点，两点间不连接
最大团数量： 补图中最大独立集数
最大团中顶点数量 = 补图的最大独立集中顶点数量
思路
最大团常用的Bron-Kerbosch算法 复杂度大约是O(3^(n/3)),不算低,大概在n==50左右就刚刚超过1e8了.
关于 Bron-Kerbosch算法
基础形式是一个递归回溯的搜索算法.通过给定三个集合 (R,P,X).N(v)表示v所直接相连的节点.
初始化集合R,X分别为空,而集合P为所有顶点的集合.
该算法的文字描述如下：从P中选出一个结点v找包含v的最大团。将v放入集合R中，并将不在N(v)的结点从P和X中移出。从剩下的P中再选出一个结点，重复上述操作。直到P成为空集。此时，若X也为空，则R是新的最大团(如果X不为空，则说明R是已经找到的最大团的一个子集)。然后，回溯到上一个选择的结点，并将集合XPR 也恢复到原来的状态，同时，将本次选择的结点从P中移出，加入X，从P中选出下一个结点重复上述操作。如果P为空集，则返回到上一级。
相关的代码(脑子)有些混乱,日后再整理
模板
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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 55;
bool mp[maxn][maxn]; // 此算法只能用邻接矩阵来存,一般节点个数不能超过50,否则很容易超时(指数复杂度)
int best, n, num[maxn];
bool dfs(int *adj, int total, int cnt) {
int t[maxn], k;
if(total == 0) {
if(cnt > best) {
best = cnt;
return true; //剪枝4
}
return false;
}
for(int i = 0; i < total; ++i) {
if(cnt+total-i <= best)
return false; //剪枝1, 若当前 顶点数量cnt 加上还能够增加的最大数量 仍小于 best则 退出并返回false
if(cnt+num[adj[i]] <= best)
return false; //剪枝3, 若当前 顶点数量cnt 加上 包含adj[i]的最大团顶点数 仍小于 best则 退出并返回false,这也是MxnimumClique 函数中循环是反向循环的原因
k = 0;
for(int j = i+1; j < total; ++j)
if(mp[adj[i]][adj[j]])
t[k++] = adj[j];
//扫描与u相连的顶点中与当前要选中的adj[i]相连的顶点adj[j]并存储到数组t[]中，数量为k
if(dfs(t, k, cnt+1))
return true;
}
return false;
}
int MaximumClique() {
int adj[maxn], k;
best = 0;
for(int i = n; i >= 1; --i) {
k = 0;
for(int j = i+1; j <= n; ++j)
if(mp[i][j])
adj[k++] = j;
//得到当前点i的所有相邻点存入adj
dfs(adj, k, 1); //每次dfs相当于必选当前i点看是否能更新best
num[i] = best;
}
return best;
}
int main() { // 主函数只需要把mp数组填好就可以
while(cin >> n && n) {
for(int i = 1; i <= n; ++i)
for(int j = 1; j <= n; ++j) {
int x;
cin >> x;
mp[i][j] = x;
}
cout << MaximumClique() << endl;
}
return 0;
}
