最大团问题 回溯法应用 作者：余新华 时间：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) 由于程序采用递归搜索，因此递归也占用了一 定的栈空间