引言(一些概念)

子图:给定无向图G=(V,E) ,存在图U=($$V_0$$, $$E_0$$)使得$$V_0 \in V$$, 并且$$E_0 \in E$$G=(V,E) ,则称图U是图G的一个子图

完全子图:也叫团,完全子图首先是子图,而且该图所有顶点两两都有边相连

最大团:使得顶点数最多的一个团称为最大团

最大团问题

解题策略

判断顶点是否可以加入团:当前要加入的顶点与之前已经加入的所有顶点都要有边相连!

代码

一定要格外注意这个限界函数的条件:

书上的代码(正确的):if (x[i] && a[t][i] == 0) { //先找已经加入集合的顶点,并且判断边是否存在

自己按照理解写的(错误的):if (x[i] != 1 || a[i][t] != 1) { //这个限界函数自己写的,是错误的

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <stdio.h>
#include <string.h>
#define N 100
int a[N][N], n, e; //将图用邻接矩阵表示出来, 顶点数,边数
int x[N], sum; //解向量,总人数
int bestn; //最优总人数

//约束函数
int Constr(int t)
{
int tmp = 1;
for(int i = 1; i < t; i++)
{
if (x[i] && a[t][i] == 0) { //先找已经加入集合的顶点,并且判断边是否存在
// if (x[i] != 1 || a[i][t] != 1) { //这个限界函数自己写的,是错误的
tmp = 0;
break;
}
}
printf("Constr: %d\n", tmp);
return tmp;
}

void Backtrack(int i)
{
if (i > n) {
bestn = sum;
return;
}
if (Constr(i)) { // 满足约束条件
sum += 1;
x[i] = 1;
Backtrack(i+1);
sum -= 1;
// x[i] = 0; //不能放在这里,因为这里是遍历该节点的左子树,并且包括该节点,此时该节点还是可选的
}
if((n - i + sum) > bestn) //如果满足限界条件,扩展右子树,那么此时该节点就没用了
{
x[i] = 0;
Backtrack(i+1);
}
}



void main()
{
printf("请输入结点个数:");
scanf("%d", &n);

printf("请输入边数:");
scanf("%d", &e);

int u, v; //临时建立图中两个结点的对应关系

//初始化
sum = 0, bestn = 0;
memset(x, 0, 100 * sizeof(int));
memset(a, 0, 100 * sizeof(int));


for(int i = 1; i <= e; i++)
{
printf("请输入第%d条边的两个端点:", i);
scanf("%d %d", &u, &v);
a[u][v] = 1, a[v][u] = 1;
}

printf("邻接矩阵为:\n");
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
printf("%d\t", a[i][j]);
}
printf("\n");
}


for(int i = 1; i <= n; i++)
printf("%d\t", x[i]);
printf("\n");
Backtrack(1);

for(int i = 1; i <= n; i++)
printf("%d\t", x[i]);

printf("国王护卫队的总人数为:%d\n", bestn);
printf("成员为:\n");
for(int i = 1; i <= n; i++)
if (x[i] == 1)
printf("%d\t", i);
for(int i = 1; i <= n; i++)
printf("\n%d\t", x[i]);

}