maxclique.cpp

回朔法解决最大团问题:G的最大团是指G中所含顶点数最多的团

// adjacency matrix representation of a graph
#include <fstream.h>
class Clique
{
 friend MaxClique(int**, int[],int);
 public:
     void Backtrack(int); 
     int **a, // 图G的邻接矩阵
         n,   // 图G的顶点数
        *x,   // 当前解
    *bestx,   // 当前最优解
        cn,   // 当前顶点数 
     bestn;   // 当前最大顶点数
};
void Clique::Backtrack(int i)
{// Backtracking code to compute largest clique.
  int j;
  if(i>n)// at leaf found a larger clique, update
    { for(j=1; j<=n; j++) bestx[j] = x[j];
      bestn = cn;     return;
    }
   int OK = 1;
   for(j=1; j<i; j++)  // check if vertex i connected to others in current clique
      if(x[j] && a[i][j]==0){ OK = 0;  break; }   // i not connected to j
   if(OK) // try x[i] = 1
     { x[i]=1;   cn++;    // add i to clique
       Backtrack(i+1);
       x[i] = 0;  cn--;
     }
   if(cn+n-i > bestn)     // try x[i] = 0
      { x[i] = 0;   Backtrack(i+1);  }
}
int MaxClique(int**a, int v[],int n)
{  Clique Y;
   Y.a = a;  Y.n=n;  Y.cn = 0;  Y.bestn = 0;   Y.bestx = v;
   Y.x = new int[n+1];
   Y.Backtrack(1);   
   return Y.bestn;
}
void main( )
{
  int **a, *v,n,e,u,d,i,j;
  ifstream in("MaxCliqueIN.dat");
  ofstream out("MaxCliqueOUT.dat");
  in>>n>>e;  out<<"Number of G'Vertices n="<<n;
  out<<"\nAdjacency matrix representation of G is\n";
  a = new int* [n+1];  v = new int[n+1];
  for(i=1; i<=n; i++)
     { v[i]=0;
       a[i]=new int[n+1]; 
       for(j=1; j<=n; j++)a[i][j]= 0;
     } 
  for(i=0; i<e; i++){ in>>u>>d; a[u][d]=1; a[d][u]=1;} // input edges
  in.close();
  for(i=1; i<=n; i++)
     { for(j=1; j<=n; j++)out<<"  "<<a[i][j]; out<<endl;  } 
  out<<"bestn=" <<MaxClique(a,v,n);
  out<<"\nMaxClique v = ( ";
  for(j=1; j<n; j++) out<<v[j]<<", "; 
  out<<v[n]<<" )\n";     out.close();     
}