最大团问题--回溯法

一、相关定义

        给定一个无向图 ，其中 V 是图的顶点集，E图的边集

        完全图：如果无向图中的任何一对顶点之间都有边，这种无向图称为完全图

        完全子图：给定无向图 ，如果 ，且对应任意  且 ，则称U是G的完全子图。（即完全子图中的任意两个顶点之间都有边）

        团（最大完全子图）：U 是 G 的团当且仅当 U 不包含在G的更大完全子图中。若存在一个最大完全子图包含U，那么 U 不是一个团。

        最大团：G 中所包含顶点数最多的团

        最大团问题是一个NP-C问题，无法在多项式时间内求出最大团，通常只能在数据规模较小的情况下适用。

二、回溯法

        算法思路：通过回溯的方法考虑每个顶点是否加入最大团的情况，因此算法的时间复杂度为 。

        首先设最大团为一个空团，往其中加入一个节点，然后依次考虑每个节点，查看该节点是否能够加入团（判断方法：该节点应当与团内每一个节点有一条边），随后向下一节点搜索，直至递归所有节点并回溯结束。

        剪枝策略：如果剩下未考虑的节点n加上当前团内的节点数小于此时计算的最大团节点数，则不需要再进行搜索。

        对于一个无向图 Ｇ＝｛V，Ｅ｝

可以看出最大团为 { 1 , 2 , 5 } { 1 , 4 , 5 }  { 2 , 3 , 5 } 即最大团不唯一。对于一个完全子图{1,2}，不是一个团，因为存在包含 {1,2} 的更大的完全子图 {1,2,5}    (区分完全子图和团)

下图：左子树时表示考虑节点i加入团中 , 右子树则不在团中        

        cn为当前团中在节点个数，bestn当前最大团中在节点个数

        

 ① 考虑 节点1 时加入当前团时，符合团的条件，则继续深搜考虑节点2，(1,2)之间存在边，符合团的条件，则继续深搜考虑 节点3 ，由于 节点3 与 节点1 之间不存在边，所以 3 不能加入团中，因此不能将 节点3 加入团中，再考虑节点 4 同理（与 节点2 不存在边），继续考虑节点5，符合团在条件，此时不能够继续搜索了，保存当前团 {1，2，5}。

        上述过程搜索前，还需判断（ cn+n-i>=bestn ），此时可以认为，即使剩下节点都考虑，最大团的节点数还是小于等于当前最大团在节点数。

② 回溯考虑其他情况，当不考虑 节点2 加入团中，往深处搜索，此时（cn+n-i<=bestn），无需再深搜考虑，其他情况同理。

#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
const int maxn=101;
int a[maxn][maxn];	//邻接矩阵
int x[maxn];
int cn,bestn,n,m;
void backtrack(int i)
{if(i>n) // 搜索完所有节点 {bestn=cn;printf("%d\n",bestn);for(int j=1;j<=n;j++){/*if(x[j]==1)printf("%d ",j);*/printf("%d ",x[j]);}printf("\n");return;}int flag=1; // 判断是否与团中节点都相连for(int j=1;j<i;j++){if( x[j] && !a[j][i])//i与j不相连{flag=0;break;}}if(flag==1)	//进入左子树{cn++;x[i]=1;backtrack(i+1);cn--;x[i]=0;}if(cn+n-i>bestn)  //剪枝{backtrack(i+1);}
}
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){ int u,v;scanf("%d%d",&u,&v);a[u][v]=1;a[v][u]=1;}backtrack(1);return 0;
}