最大团问题（回溯法/分支限界法）

问题描述 图G=（V，E）的一个团是图G的一个完全子图，即该子图中任意两个相异的顶点都有一条边相连。最大团问题就是要找出图G中顶点数最多的一个团。 基本要求 (1) 用回溯法来求解最大团问题。 (2) 用分支限界法来求解最大团问题。 测试数据 由读者给定若干连通图。 实现提示 本课程设计的实现主要包括以下主要过程： (1) 关于解的编码形式（对应顶点i 的变量x[i]=1当且仅当顶点i属于找到的最大团）。 (2) 设计合适的上界函数，即如何确定当前团最大顶点数的上界。

# include 
# include 
# include 
# include 
using namespace std;

typedef struct{
int v;
int e;
int a[50][50];  //定义图
int bestx[50];  //最优解
}MGraph;

void Creat（MGraph &G）{
    int ij;
	ifstream fin（“data.txt“）;
	if（!fin）
	{
		cout<<“不能打开文件:“<<“data.txt“<		exit（1）;
	}
	fin>>G.v;
	for（int i=1;i<=G.v;i++）
		for（int j=1;j<=G.v;j++）
			fin>>G.a[i][j];
    for（i=1;i<=G.v;i++）   //初始化
    {
	    G.bestx[i]=0;
	}
    cout<<“输入初始化无向图矩阵为:“<    for（i=1;i<=G.v;i++）
    {
        for（j=1;j<=G.v;j++）
            cout<        cout<    }
}

struct BNode    
{              
 BNode *parent;
 bool LChild;
};

struct CliqueNode  //定义优先队列类型为CliqueNode
{
 int csuslevel;  //分别是当前团顶点数，最大顶点上界，和所在的层次
 BNode *p;         //记录该点的情况是左孩子还是右孩子，父母是谁 
 bool operator<（const CliqueNode& b） const  //<号重载建立大根堆
 { 
  if（b.us>us）  return true;
  if（b.us==us&&b.cs>cs） return true;
  else return false;
 }
};

void Search（MGraph &G）
{
 
 BNode *B=new（BNode）;  //定义B代表记录的队列情况
 int ji=1;
 int cs=0bestn=0; 
 int flag=1;  
 priority_queue Q;  //定义优先队列Q
 B->LChild=false;  //初始化
 B->parent=NULL;
 while（i!=G.v+1）
 {
  flag=1;
  BNode *C=B;  //把当前点的数据给C，C为中间变量
  for（j=i-1;j>0;C=C->parentj--）
  if（C->LChild&&G.a[i][j]==0）  //如果不满足就停止
  {
   flag=0;
   break;
  }
  if（flag） //满足条件
  {
   CliqueNode *D=new（CliqueNode）;  //定义一个节点D
   D->p=new（BNode）;
   if（cs+1>bestn）bestn=cs+1;
   D->cs=cs+1; 
   D->level=i+1;
      D->p->LChild=true;
            D->p->parent=B;
   D->us=cs+1+G.v-i;
   Q.push（*D）;  //进队列
  }
  if（cs+G.v-i>bestn ）  //不满足条件但是还是可能有最优解
  {
   CliqueNode *D=new（CliqueNode）;  //定义一个节点D
   D->p=new（BNode）;
            D->cs=cs;  
   D->level=i+1;
   D->p->LChild=false;
            D->p->parent=B;
   D->us=cs+G.v-i;
   Q.push（*D）;  //进队列
  }
 
  CliqueNode N;
  N=Q.top（）;   //取队顶元素，最大堆
  Q.pop（）;       //删除队顶元素
  B=N.p;        //记录当前团的信息
  cs=N.cs;      //记录当前团的顶点数
  i=N.level;    //所在的层次
 }
 for（j=G.v;j>0;j--）  //保存最优解
 {
  G.bestx[j]=B->LChild;
  B=B->parent;
  bestn=cs;
 }
}
void main（）{
        MGraph G;
        Creat（G）;
        Search（G）;
cout<<“最大团方案为:“<        for（int i=G.v;i>0;i--）
           if（G.bestx[i]==true）{
                         cout<             }
cout<getch（）;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      39424  2010-07-15 14:39  实验设计-MCP（回溯法）\Debug\实验设计-MCP（回溯法）.exe

     文件     387420  2010-07-15 14:39  实验设计-MCP（回溯法）\Debug\实验设计-MCP（回溯法）.ilk

     文件     543744  2010-07-15 14:39  实验设计-MCP（回溯法）\Debug\实验设计-MCP（回溯法）.pdb

     文件      25069  2010-07-14 21:03  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\data.png

     文件         58  2010-07-14 19:43  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\data.txt

     文件         56  2010-07-14 20:42  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\data2.txt

     文件       7422  2010-07-15 14:39  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\Debug\BuildLog.htm

     文件      46304  2010-07-15 14:39  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\Debug\MCP（回溯法）.obj

     文件         67  2010-07-15 14:39  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\Debug\mt.dep

     文件     306176  2010-07-15 14:39  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\Debug\vc90.idb

     文件     225280  2010-07-15 14:39  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\Debug\vc90.pdb

     文件        621  2010-07-15 14:39  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\Debug\实验设计-MCP（回溯法）.exe.intermediate.manifest

     文件       1680  2010-07-15 14:39  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\MCP（回溯法）.cpp

     文件       3791  2010-07-15 11:47  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\实验设计-MCP（回溯法）.vcproj

     文件       1413  2010-07-15 15:04  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\实验设计-MCP（回溯法）.vcproj.E305-115.user.user

     文件       1413  2010-07-15 11:48  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）\实验设计-MCP（回溯法）.vcproj.Moese-Wi.Moese.user

     文件     592896  2010-07-15 15:26  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）.ncb

     文件        947  2010-07-14 19:22  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）.sln

    ..A..H.     15360  2010-07-15 15:04  实验设计-MCP（回溯法）\实验设计-MCP（回溯法）.suo

     文件      79360  2010-07-15 14:37  实验设计-MCP（分支限界法）\Debug\实验设计-MCP（分支限界法）.exe

     文件     500708  2010-07-15 14:37  实验设计-MCP（分支限界法）\Debug\实验设计-MCP（分支限界法）.ilk

     文件     699392  2010-07-15 14:37  实验设计-MCP（分支限界法）\Debug\实验设计-MCP（分支限界法）.pdb

     文件         58  2010-07-14 19:43  实验设计-MCP（分支限界法）\实验设计-MCP（分支限界法）\data.txt

     文件         56  2010-07-14 20:42  实验设计-MCP（分支限界法）\实验设计-MCP（分支限界法）\data2.txt

     文件       7836  2010-07-15 14:37  实验设计-MCP（分支限界法）\实验设计-MCP（分支限界法）\Debug\BuildLog.htm

     文件     262936  2010-07-15 14:37  实验设计-MCP（分支限界法）\实验设计-MCP（分支限界法）\Debug\MCP（分支限界法）.obj

     文件         67  2010-07-15 14:37  实验设计-MCP（分支限界法）\实验设计-MCP（分支限界法）\Debug\mt.dep

     文件     338944  2010-07-15 14:37  实验设计-MCP（分支限界法）\实验设计-MCP（分支限界法）\Debug\vc90.idb

     文件     258048  2010-07-15 14:37  实验设计-MCP（分支限界法）\实验设计-MCP（分支限界法）\Debug\vc90.pdb

     文件        621  2010-07-15 14:37  实验设计-MCP（分支限界法）\实验设计-MCP（分支限界法）\Debug\实验设计-MCP（分支限界法）.exe.intermediate.manifest

............此处省略66个文件信息