回溯法解最大团问题.cpp

算法分析中

/*
无向图G的最大团和最大独立子集问题都可以用回溯法在O(n2^n)时间内解决。
子集树就有2^n个结点，n是限界函数时间
图G的最大团和对大独立子集问题都可以看作是图G的顶点集v的子集选取问题
因此可以用子集树表示问题的解空间
与解装载问题很相似，设当前扩展结点z位于解空间树的第i层。在进入左子树
前，必须确认从顶点i到已经选入的顶点集合中每一个每一个顶点都有边相连。在
进入右子树前，必须确认还有足够多的可选择顶点使得算法有可能在右子树中
找到更大的团.
具体实现时：
用邻接矩阵表示图G。
函数Backtrack是类Clique的私有成员函数
而函数MaxClique负责有关变量的初始化以及调用Backtrack进行搜索
整型数组v返回所找到的最大团。v[i]=1当前仅当顶点i属于找到的最大团
**/
#include<iostream>
using namespace std;
class Clique
{
	friend MaxClique(int **,int [],int);
private:
	void Backtrack(int i);
	int **a;
	//图G的邻接矩阵
	int n;
	//图G的顶点数
	int *x;
	//当前解
	int *bestx;
	//当前最优解
	int cn;
	//当前顶点数
	int bestn;
	//当前最大顶点数

};

void Clique::Backtrack(int i)
{
	//计算最大团
	if ( i > n )
	{
		for( int j = 1; j <= n; ++j )
		{
			bestx[j] = x[j];
		}
		bestn = cn;
		return;
	}
	//检查顶点i与当前团的连接
	int OK = 1;
	for( int j = 1; j < i; ++j )
	{
		if (x[j] && a[i][j] ==0 )
		//只要新结点和已经入团的任何一个结点没有边连时，就不能加入
		{
			OK = 0;
			break;
		}
	}

	if ( OK )
		//新结点被加入了团
	{
		x[i] = 1;
		cn++;
		Backtrack(i+1);
		//回溯返回上层要恢复上层所在的信息
		x[i]=0;
		cn--;
	}
	
	if ( cn+n-i > bestn )
		//计算当前选中的结点和剩余的结点和大于最大值时，进入
		//右子树才比较有意义
	{
		x[i] = 0;
		Backtrack(i+1);
	}
}

int MaxClique(int **a,int v[],int n)
{
	Clique Y;
	Y.x = new int[n+1];
	Y.a = a;
	Y.n = n;
	Y.cn = 0;
	Y.bestn = 0;
	Y.bestx = v;
	Y.Backtrack(1);
	delete []Y.x;
	return Y.bestn;
}

int main()
{
	int V[6][6] =
	{
		{0,2,0,0,0,0},
		{0,1,1,0,1,1},
		{0,1,1,1,0,1},
		{0,0,1,1,0,1},
		{0,1,0,0,1,1},
		{0,1,1,1,1,1}
	};
	//cout<<*(V+1)<<endl;
	/*
	V指向第0行的首地址
	*V第0行第0列的地址
	**V第0行第0列的元素
	*/
	//cout<<*V<<endl;
	int **a = new int*[6];
	for( int j = 0; j < 6; ++j )
	{
		a[j] = new int[6];
	}
	for( j = 0; j < 6; ++j )
		for( int k = 0; k < 6; ++k )
			a[j][k] = V[j][k];
	//int **a = V;
	//常量指针，不能赋值给变量
	int b[6] = {0,0,0,0,0,0};
	int *c = b;
	int n = 5;
	MaxClique(a,b,n);
	for(int i = 0; i <= 5; ++i)
	{
		if (b[i] == 1)
		{
			cout<<i<<endl;
		}
	}
	return 0;
}