用回溯法解决最大团问题

宁夏师范学院数学与计算机科学学院《算法分析与设计》实验报告实验序号：10实验项目名称：用回溯法解决最大团问题学号姓名专业、班实验地点指导教师时间2014.06.19一、实验目的及要求（1）理解算法复杂度的概念（2）掌握算法复杂度计算的方法二、实验设备（环境）及要求1、环境要求：硬件：PC（PII以上，128M以上内存）、因特网接入；软件：WindowsXP操作系统、Office2003、多媒体播放软件。三、实验内容与步骤#includestdio.h#defineN5intx[N+1];//当前解intcc;//当前顶点数intbestc;//当前对大顶点数intbestx[N+1];//当前最优解inta[N+1][N+1];//邻接矩阵，存储无向图的边信息voidbacktrack(inti){//遍历第i层的子树if(iN){//到达叶子结点intj;printf(最大团为:);for(j=1;j=N;j++){if(x[j]==1)printf(%3d,j);//bestx[j]=x[j];}bestc=cc;printf(\n);}else{//左子树intk=1,j;//判断顶点1:i-1与i是否有边，若其中有一个顶点与i无边，则k=0for(j=1;j=i-1;j++){if(x[j]==1&&a[i][j]==0){k=0;break;}}if(k==1)//k!=0{//进入左子树x[i]=1;cc++;backtrack(i+1);cc--;//为进入下一层做准备}if(cc+N-i=bestc){//进入右子树x[i]=0;backtrack(i+1);}}}intmaxClique(){voidinputAjac();//初始化cc=0;bestc=0;inputAjac();backtrack(1);returnbestc;}voidinputAjac(){inti,j;printf(输入1表示有边,0表示无边：\n);for(i=1;i=N;i++){for(j=i+1;j=N;j++){printf(请输入第%d顶点到第%d顶点边：,i,j);scanf(%d,&a[i][j]);a[j][i]=a[i][j];}}}voidmain(){printf(%d个顶点无向图的最大团个数为：%d\n,N,maxClique());}四、实验结果与数据处理五、分析与讨论1、在解决最大团问题之前首先要了解几个最基本的概念，团、最大团、空子图、独立集、最大集,。给定无向图G=（V,E）。（1）团：如果UV，且对任意u,vU有（u，v）E，则称U是G的完全子图。G的完全子图U是G的团；当且仅当U不包含在G的更大的完全子图中。（2）最大团：是指G中所含顶点数最多的团。（3）空子图：如果UV，且对任意u,vU有（u，v）E，则称U是G的空子图。（4）独立集：G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。（5）最大集：是G中所含顶点数最多的独立集。2、无向图G的最大团和最大独立集问题都可以用回溯法在O(n2n)时间内解决，图G的最大团和最大独立集问题都可以看作是图G顶点集V的自己选取问题。因此，可以用子集树表示问题的解空间。六、教师评语成绩签名：日期：年月日