中北大学算法分析与设计实验报告六（最大团问题）-Toy模板网

这篇具有很好参考价值的文章主要介绍了中北大学算法分析与设计实验报告六（最大团问题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

中北大学算法分析与设计实验报告六（最大团问题）

1.实验名称

实验六回溯与分支限界算法实验

2.实验目的

题目：最大团问题
强化学生利用回溯算法和优化处理实际问题的能力。

3.训练知识点集群

（1）根据实验内容设计算法伪代码进行算法描述；
（2）利用C++/C/Java等编程语言对算法伪代码进行工程化实现；
（3）输入测试用例对算法进行验证；
（4）列出算法时间复杂度模型并与计算机运行统计时间进行对比分析。

4.实验内容

给定一个无向图G=(V,E)。若 ,且对任意的,都有边 ,则称U是图G的一个完全子图。G的完全子图U是一个图，当且仅当U不包含在G的更大的完全子图中。G的最大团是指包含顶点数最多的团。对给定的无向图，找出最大团中定点的个数。

5.实验原理

算法思路：
首先最大团是一个空团（即不包含任何一个顶点的团），然后把每一个顶点依次加入团中。加入当前顶点i时，需要考虑当前顶点i是否与所有已经加入团的顶点邻接。如果不邻接，直接跳过该顶点，考虑下一个顶点。如果邻接，还需要考虑两种情况：一种是把当前顶点i加入团中，然后递归考虑后面的顶点；另一种是不把当前顶点i放入团中，然后递归考虑后面的顶点。直到所有的顶点都考虑完后，判断当前的最有解是否比之前的最优解更优。如果更优，用当前最优解替代之前的最优解，回溯；如果不是更优，回溯。直到将整个子集树遍历完，算法结束。

约束函数：当前顶点i要与选入顶点集的每一个顶点邻接。
上界函数：有足够多的可选顶点使有可能在右子树找到最大团。

6.源代码实现

#include <stdio.h>
#include <string.h>
int book[25][25],visit[25],que[25];//que数组表示在图中的点，book记录边，visit记录访问过的点
int n,m,max;
void dfs(int x,int sum){
    if(x>n){//搜完所有的点，递归出口
         max=sum;
         return ;
    }
    int vt=0;
    for(int j=0;j<sum;j++){//判断与图中的点是否两两相通
        if(book[x][que[j]] == 0){
                vt=1;
                break;
                }
            }
    if(vt == 0)//相通进入que数组，并且图中顶点+1
    {
        visit[x]=1;
        que[sum]=x;
        dfs(x+1,sum+1);
    }
      if(sum+n-x >max)//剪枝
         dfs(x+1,sum);
}
int main(){
    int t,vi=0;
    scanf("%d",&t);
    while(t--){
        scanf("%d %d",&n,&m);
        int x,y;
        memset(visit,0,sizeof(visit));
        memset(book,0,sizeof(book));
        max=0;
        for(int i=1;i<=m;i++){
            scanf("%d %d",&x,&y);
            book[x][y]=1;
            book[y][x]=1;
        }
             dfs(1,0);
        vi++;
       printf("Case %d: %d\n",vi,max);
    }
    return 0;
}