最大子团问题回溯法_目前的团扩张为极大团的顶点数上界

问题：一个无向图 G=(V，E)，V 是点集，E 是边集。取 V 的一个子集 U，若对于 U 中任意两个点 u 和 v，有边 (u,v)∈E，那么称 U 是 G 的一个完全子图。 U 是一个团当且仅当 U 不被包含在一个更大的完全子图中。
G的最大团指包含顶点数最多的一个团。

• 解法：
• <x1,x2…xn>为0-1向量, xk=1表示顶点k在最大团中。
• 搜索树为子集树，
• 约束条件：当前顶点与团中的每个顶点都有边相连，
• 界： 当前极大团内的顶点数，
• 代价函数：当前团可能扩展为极大团的顶点数上界，F=Cn+n-k,(Cn为当前团顶点数，k结点层数）。
• 最坏情况 O(n2ⁿ )。
• 
• B为界，F为代价函数。
  c++代码：

#include<bits/stdc++.h>
using namespace std;
#define M 101

bool a[M][M];//图的邻接矩阵
bool x[M]; //当前 解 
int cn;//当前团的顶点数
int bestn, bestx[M];//当前的最优解
int n, m;//n图G的顶点数 
void backtrack(
1
2
3
4
5
6
7
8
9