回溯算法 --- 例题6.最大团问题

一.问题描述

给定无向图G=(V, E), U?V, 若对任意u, v∈U, 有(u,v) ∈ E, 则称U是G的一个完全子图.
G的完全子图U是G的一个团当且仅当U不包含在G的更大的完全子图中,G的最大团是指G中所含顶点数最多的团.

二.解题思路

无向图G的最大团和最大独立集问题都可以用回溯法在O(n2^n)时间内解决.图G的最大团和最大独立集问题都可以看做图G的顶点集V的子集选取问题.因此,我们可以用子集树表示问题的解空间.

解最大团问题的回溯法和解装载问题的回溯法十分相似.设当前扩展结点Z位于解空间树的第i层.在进入左子树前,必须确认还有足够多的可选择顶点,使得算法有可能在右子树中找到更大的集.

具体代码如下:

// 最大团问题
#include
using namespace std;
class Clique
{
    friend int MaxClique(int **, int *, int);
    private:
        void Backtrack(int i);
        int **a,        //图G的邻接矩阵
            n,          //图G的顶点数
            *x,         //当前解
            *bestx,     //当前最优解
            cn,         //当前顶点数
            bestn;      //当前最大顶点数
};
void Clique::Backtrack(int i)   //计算最大团
{
    static int k = 1;
    if(i > n)
    {
        cout<<"第"<= bestn)  //如果右子树中剩余所有结点个数加起来大于等于当前最大顶点数,那么进入右子树.
    {
        cout<<"进入右子树深入一层,将到达第"<>n && n)
    {
        cout<<"请输入邻接矩阵"<>a[i][j];
        int *v = new int[n+1];
        for(int i=0; i<=n; i++) v[i] = 0;
        int ans = MaxClique(a, v, n);
        cout<<"最大团中顶点个数为:"<