顶点之间都有边这种无向图称为完全图

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

二、回溯法

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

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

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

对于一个无向图

即最大团不唯一。

对于一个完全子图{1,2}不是一个团因为存在包含

{1,2}

时加入当前团时符合团的条件则继续深搜考虑节点2(1,2)之间存在边符合团的条件则继续深搜考虑

节点3

不存在边继续考虑节点5符合团在条件此时不能够继续搜索了保存当前团

cnn-ibestn

此时可以认为即使剩下节点都考虑最大团的节点数还是小于等于当前最大团在节点数。

回溯考虑其他情况当不考虑

加入团中往深处搜索此时cnn-ibestn无需再深搜考虑其他情况同理。

#includeiostream

{bestncn;printf(%d\n,bestn);for(int

,j);*/printf(%d

!a[j][i])//i与j不相连{flag0;break;}}if(flag1)

//进入左子树{cn;x[i]1;backtrack(i1);cn--;x[i]0;}if(cnn-ibestn)

//剪枝{backtrack(i1);}

u,v;scanf(%d%d,u,v);a[u][v]1;a[v][u]1;}backtrack(1);return