最大团问题回溯法应用作者：余新华时间：2005-5-28.

最大团问题回溯法应用作者：余新华时间：

问题描述给定无向图G=(V，E)。如果U V，且对任意u，v U 有(u，v) E，则称U 是G 的完全子图。G 的
完全子图U是G的团当且仅当U不包含在G 的更大的完全子图中。G 的最大团是指G中所含顶点数最多的团。编程任务：对于给定的无向图G,编程计算G 的最大团

问题示例 1 2 5 4 1 5 1 2 5 3 4 1 （b）（c） 2 5 3 （a）图a是一个无向图，图b、c、d都是图a的团，且都是最大团（d）

程序思路首先设最大团为一个空团，往其中加入一个顶点，然后依次考虑每个顶点，查看该顶点加入团之后仍然构成一个团，如果可以，考虑将该
顶点加入团或者舍弃两种情况，如果不行，直接舍弃，然后递归判断下一顶点。对于无连接或者直接舍弃两种情况，在递归前，可采用剪枝策略来避免无效搜索

判断顶点是否可入团为了判断当前顶点加入团之后是否仍是一个团，只需要考虑该顶点和团中顶点是否都有连接。代码如下：
for(j=1;j<i;j++) if(x[j]&&a[i][j]==0) {ok=0;break;}

剪枝策略程序中采用了一个比较简单的剪枝策略，即如果剩余未考虑的顶点数加上团中顶点数不大于当前解的顶点数，可停止继续深度搜索，否则继续深
度递归，程序代码如下： if(cn+n-i>bestn) { x[i]=0;//设置标志 backtrack(i+1);//递归判断下一顶点 }

递归结束条件当搜索到一个叶结点时，即可停止搜索，此时更新最优解和最优值，程序代码如下： if(i>n) {
for(j=1;j<=n;j++) bestx[j]=x[j]; bestn=cn; return; }

时间复杂度由于最大团问题是一个子集树问题，每个可行叶结点都做一次bestx更新，因此可知算法的时间复杂度为O(n2n)

空间复杂度在程序中使用邻接矩阵才存储图，用两个一维数组存储当前解和最优解信息，因此可知所用的存储空间为O(n2)
由于程序采用递归搜索，因此递归也占用了一定的栈空间

Presentation on theme: "最大团问题回溯法应用作者：余新华时间：2005-5-28."— Presentation transcript: