cclique.h

用回溯法实现最大团问题

class clique
{
	public:
		clique(int **,int [],int);
		~clique();
		void backtrack(int i);
		void print();
	private:
		int **a;//图g的邻接矩阵
		int n;//图g顶点数
		int *x;//当前解
		int *bestx;//当前最优解
		int cn;//当前顶点数
		int bestn;//当前最大顶点数
		int **A;
		int N;
		int *X;
};
clique::clique(int **a,int v[],int n)
{
	cout<<"*"<<endl;
		A=a;
		N=n;
		X=new int[N+1];
		cn=0;
		bestx=new int[N+1];
		v=new int[N+1];
		/*for(int i=0;i<=N;i++)
		{
			X[i]=1;
			v[i]=0;
			bestx[i]=v[i];
		}*/
		cout<<"*"<<endl;
	
}
clique::~clique()
{
	delete []x;
	delete []bestx;
}
void clique::print()
{
	if(bestx!=0)
	{
		cout<<"最大团是："<<endl;
		cout<<bestx[1]<<endl;
		for(int i=2;i<=N;i++)
		{
			cout<<bestx[i]<<' '<<endl;
		}
		cout<<endl;
	}
	else
		cout<<"问题无解!"<<endl;
}
void clique::backtrack(int i)//回朔方程
{
	if(i>N)//判断是否有必要继续进行回朔
	{
		for(int j=1;j<=N;j++)//如果i小于总顶点的个数就执行循环
			bestx[j]=X[j];//并且将当前解赋值给当前最优解
		bestn=cn;//并且将当前顶点个数记为最大顶点个数
		return;
	}
	int ok=1;
	for(int j=1;j<i;j++)//进行循环终结点为函数的参数
		if(X[j]&&A[i][j]==0)//如果i与j是不相连的
		{
			ok=0;//将ok变为假
			break;//并且跳出循环
		}
	if(ok)//如果ok为真
	{
		X[i]=1;	//把相对的数组的位置变为真
		cn++;//并且当前点数增加一
		backtrack(i+1);//再马上递归调用原函数继续判断下个个数的顶点数是否适合组成最大团
		X[i]=0;//要是得出的数组相对应的位置为假
		cn--;//当前点减小一
	}
		if(cn+N-i>bestn)//如果当前点加上总共点的个数减去参数的值比当前最大的点数大   当出现不符合组成最大团的点的时候就是用这个函数将其踢走
		{
			X[i]=0;//相对应数组的位置变成假
			backtrack(i+1);//然后调用下个点的个数
		}

}