/*
無向圖G的最大團和最大獨立子集問題都可以用回溯法在O(n2^n)時間內(nèi)解決。
子集樹就有2^n個結(jié)點，n是限界函數(shù)時間
圖G的最大團和對大獨立子集問題都可以看作是圖G的頂點集v的子集選取問題
因此可以用子集樹表示問題的解空間
與解裝載問題很相似，設當前擴展結(jié)點z位于解空間樹的第i層。在進入左子樹
前，必須確認從頂點i到已經(jīng)選入的頂點集合中每一個每一個頂點都有邊相連。在
進入右子樹前，必須確認還有足夠多的可選擇頂點使得算法有可能在右子樹中
找到更大的團.
具體實現(xiàn)時：
用鄰接矩陣表示圖G。
函數(shù)Backtrack是類Clique的私有成員函數(shù)
而函數(shù)MaxClique負責有關變量的初始化以及調(diào)用Backtrack進行搜索
整型數(shù)組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的頂點數(shù)
	int *x;
	//當前解
	int *bestx;
	//當前最優(yōu)解
	int cn;
	//當前頂點數(shù)
	int bestn;
	//當前最大頂點數(shù)

};

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 )
		//只要新結(jié)點和已經(jīng)入團的任何一個結(jié)點沒有邊連時，就不能加入
		{
			OK = 0;
			break;
		}
	}

	if ( OK )
		//新結(jié)點被加入了團
	{
		x[i] = 1;
		cn++;
		Backtrack(i+1);
		//回溯返回上層要恢復上層所在的信息
		x[i]=0;
		cn--;
	}
	
	if ( cn+n-i > bestn )
		//計算當前選中的結(jié)點和剩余的結(jié)點和大于最大值時，進入
		//右子樹才比較有意義
	{
		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;
}