WizenZhang
10/4/2018 - 1:39 PM

【回溯法】最大团问题【5.7】

给定无向图G=(V, E)，其中V是非空集合，称为顶点集；E是V中元素构成的无序二元组的集合，称为边集，无向图中的边均是顶点的无序对，无序对常用圆括号“( )”表示。如果U∈V，且对任意两个顶点u，v∈U有(u, v)∈E，则称U是G的完全子图(完全图G就是指图G的每个顶点之间都有连边)。G的完全子图U是G的团当且仅当U不包含在G的更大的完全子图中。G的最大团是指G中所含顶点数最多的团。

5d7.txt
content_copyfile_download
0 1 0 1 1 
1 0 1 0 1
0 1 0 0 1
1 0 0 0 1
1 1 1 1 0
MaxClique.cpp
content_copyfile_download
//最大团问题 回溯法求解
#include "stdafx.h"
#include <iostream>
#include <fstream>
using namespace std;
 
const int N = 5;//图G的顶点数
ifstream fin("5d7.txt");   
 
class Clique
{
	friend int MaxClique(int **,int[],int);
	private:
		void Backtrack(int i);
		int **a,		//图G的邻接矩阵
			n,			//图G的顶点数
			*x,			//当前解
			*bestx,		//当前最优解
			cn,			//当前顶点数
			bestn;		//当前最大顶点数
};
 
int MaxClique(int **a, int v[], int n);
 
int main()
{
	int v[N+1];
	int **a = new int *[N+1];  
    for(int i=1;i<=N;i++)    
    {    
        a[i] = new int[N+1];    
    } 
	
	cout<<"图G的邻接矩阵为:"<<endl;
	for(int i=1; i<=N; i++)  
    {  
        for(int j=1; j<=N; j++)  
        {  
            fin>>a[i][j];      
            cout<<a[i][j]<<" ";    
        }  
        cout<<endl;  
    }
 
	cout<<"图G的最大团解向量为："<<endl;
	cout<<"图G的最大团顶点个数为："<<MaxClique(a,v,N)<<endl;
 
	for(int i=1;i<=N;i++)    
    {    
        delete[] a[i];   
    } 
	delete []a;
	return 0;
}
 
// 计算最大团
void Clique::Backtrack(int i)
{
	if (i > n) // 到达叶结点
	{
		for (int j = 1; j <= n; j++)
		{
			bestx[j] = x[j];
			cout<<x[j]<<" ";
		}
		cout<<endl;
		bestn = cn;
		return;
	}
	// 检查顶点 i 与当前团的连接
	int OK = 1;
	for (int j = 1; j < i; j++)
	if (x[j] && a[i][j] == 0)
	{
		// i与j不相连
		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
	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;
}