余新华-5.2.txt

这是很不错的计算机算法

/*最大团问题求解程序*/
/*本程序运行前提：
  在源程序目录下存在input.txt文件，并且该文件已经按一定格式存储若干值
/*本程序在tc++3.0和vc++6.0上运行通过*/
#include<fstream.h>
#include<stdlib.h>
#include<iomanip.h>

class clique
{
  private:
    int **a;//邻接矩阵 
    int n;//图顶点个数 
    int *x;//当前解 
    int *bestx;//最优解 
    int cn;//当前团的顶点数 
    int bestn;//当前最大团的顶点数 
  public:
    clique();//构造函数 
    void backtrack(int i);//递归函数 
    void ouputtofile();//输出函数 
    ~clique();//析构函数 
};

/*构造函数的定义*/ 
clique::clique()
{
  int m;//边数 
  int i,j;//循环控制变量 
  int v1,v2;//构成边的两顶点 
  ifstream fin("input.txt",ios::nocreate);//打开输入文件
  if(!fin) //如果文件不存在 
  {
    cerr<<"文件不存在";
    exit(-1);
  } 
  fin>>n>>m;//读入顶点数和边数 
  if(!(a=new int*[n+1]))//分配二维数组a 
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  for(i=0;i<=n;i++)
    if(!(a[i]=new int[n+1]))//为每个一维数组分配空间
    {
      cerr<<"insufficient memory!"<<endl;//分配不成功，退出
      delete[] a;
      exit(-1);
    }
  for(i=1;i<=n;i++)//邻接矩阵初始化 
    for(j=1;j<=n;j++)
      a[i][j]=0;
  for(i=1;i<=m;i++)//邻接矩阵的建立 
  {
    fin>>v1>>v2;//读入每条边信息 
    a[v1][v2]=a[v2][v1]=1;//对相应元素赋值 
  }
  if(!(x=new int[n+1]))//分配x数组 
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  if(!(bestx=new int[n+1]))//分配bestx数组
  {
    cerr<<"insufficient memory!"<<endl;//分配不成功，退出
    exit(-1);
  }
  cn=bestn=0;//初始化 
  fin.close();//关闭输入文件
}
  

/*递归函数的定义*/ 
void clique::backtrack(int i)
{
  int j;//循环控制变量 
  if(i>n)//考虑完所有顶点，此时的解必定是更优解 
  {
    for(j=1;j<=n;j++)//设置新的bestx 
      bestx[j]=x[j];
    bestn=cn;//设置新的bestn 
    return;
  }
  int ok=1;//设置标志表示顶点i和当前团是否连接 
  for(j=1;j<i;j++)
    if(x[j]&&a[i][j]==0) {ok=0;break;}//如果不连接，修改标志并退出循环 
  if(ok)//如果有连接则将顶点i加入团中 
  {
    x[i]=1;//设置标志 
    cn++;//顶点数加1 
    backtrack(i+1);//递归判断下一顶点 
    x[i]=0;//考虑顶点i不加入团的情况 
    cn--;//顶点数还原 
  }
  if(cn+n-i>bestn)//如果无连接或者顶点i不加入团中，并且团的顶点个数有可能超过当前最大团顶点数 
  {
    x[i]=0;//设置标志 
    backtrack(i+1);//递归判断下一顶点 
  }
}

/*输出函数的定义*/ 
void clique::ouputtofile()
{
  ofstream out("output.txt");//创建输出文件
  out<<bestn<<endl;//输出最大团顶点数 
  for(int i=1;i<=n;i++)
  {
    out<<bestx[i]<<" ";//输出最优解信息 
  }
  out.close();//关闭输出文件 
}

/*析构函数的定义*/ 
clique::~clique()
{
  delete[] x;//释放x所占内存 
  delete[] bestx;//释放bestx所占内存 
  for(int i=0;i<=n;i++)//释放二维a数组所占内存 
    delete[] a[i];
  delete[] a;
}

/*主程序部分*/ 
int main()
{
  clique cli;//创建类clique的实例 
  cli.backtrack(1);//调用递归函数计算最大团 
  cli.ouputtofile();//输出解信息 
  return 0;
}