问题描述给定无向图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中所含顶点数最多的团。
如果U∈V且对任意u，v∈U有(u, v)不属于E，则称U是G的空子图。
G的空子图U是G的独立集当且仅当U不包含在G的更大的空子图中。
G的最大独立集是G中所含顶点数最多的独立集。
对于任一无向图G=(V, E)，其补图G'=(V', E')定义为：V'=V，且(u, v)∈E'当且仅当(u, v)∈E。
如果U是G的完全子图，则它也是G'的空子图，反之亦然。
因此，G的团与G'的独立集之间存在一一对应的关系。
特殊地，U是G的最大团当且仅当U是G'的最大独立集。
例：如图所示，给定无向图G={V, E}，其中V={1,2,3,4,5}，E={(1,2), (1,4), (1,5),(2,3), (2,5), (3,5), (4,5)}。
根据最大团(MCP)定义，子集{1,2}是图G的一个大小为2的完全子图，但不是一个团，因为它包含于G的更大的完全子图{1,2,5}之中。
{1,2,5}是G的一个最大团。
{1,4,5}和{2,3,5}也是G的最大团。
右侧图是无向图G的补图G'。
根据最大独立集定义，{2,4}是G的一个空子图，同时也是G的一个最大独立集。
虽然{1,2}也是G'的空子图，但它不是G'的独立集，因为它包含在G'的空子图{1,2,5}中。
{1,2,5}是G'的最大独立集。
{1,4,5}和{2,3,5}也是G'的最大独立集。
算法设计最大团问题的解空间树也是一棵子集树。
子集树的根结点是初始扩展结点，对于这个特殊的扩展结点，其cliqueSize的值为0。
算法在扩展内部结点时，首先考察其左儿子结点。
在左儿子结点处，将顶点i加入到当前团中，并检查该顶点与当前团中其它顶点之间是否有边相连。
当顶点i与当前团中所有顶点之间都有边相连，则相应的左儿子结点是可行结点，将它加入到子集树中并插入活结点优先队列，否则就不是可行结点。
接着继续考察当前扩展结点的右儿子结点。
当upperSize>bestn时，右子树中可能含有最优解，此时将右儿子结点加入到子集树中并插入到活结点优先队列中。
算法的while循环的终止条件是遇到子集树中的一个叶结点(即n+1层结点)成为当前扩展结点。
对于子集树中的叶结点，有upperSize＝cliqueSize。
此时活结点优先队列中剩余结点的upperSize值均不超过当前扩展结点的upperSize值，从而进一步搜索不可能得到更大的团，此时算法已找到一个最优解。
算法具体实现如下：1、1.template<class T>2.class MaxHeap3.{4.public:5.MaxHeap(int MaxHeapSize = 10);6.~MaxHeap() {delete[] heap;}7.int Size() const{return CurrentSize;}8.9.T Max()10.{11.MaxSize = MaxHeapSize;12.heap = new T[MaxSize+1];13.CurrentSize = 0;14.}15.16.template<class T>17.MaxHeap<T>& MaxHeap<T>::Insert(const T& x)18.{19.if(CurrentSize == MaxSize)20.{21.cout<<"no space!"<<endl;22.return*this;23.}24.25.26.27.delete[] heap;28.heap = a;29.CurrentSize = size;30.MaxSize = ArraySize;31.32.// 从最后一个内部节点开始，一直到根，对每个子树进行堆重整33.for(int i = CurrentSize/2; i >= 1; i--)34.{35.T y = heap[i]; // 子树根节点元素36.// find place to put y37.int c = 2*i; // parent of c is target38.// location for y39.while(c <= CurrentSize)40.{41.// heap[c] should be larger sibling42.if(c < CurrentSize && heap[c] < heap[c+1])43.{44.c++;45.}46.// can we put y in heap[c/2]47.if(y >= heap[c])48.{49.break; // yes50.}51.52.// no53.heap[c/2] = heap[c]; // move child up54. c *= 2; // move down a level55.}56.heap[c/2] = y;57.}58.}2、1.//最大团问题优先队列分支限界法求解2.#include ""3.#include ""4.#include <iostream>5.#include <fstream>ing namespace std;7.8.const int N = 5;//图G的顶点数9.ifstream fin("");10.11.class bbnode12.{13.friend class Clique;14.private:15.bbnode *parent; //指向父节点的指针16.bool LChild; //左儿子节点标识17.};18.19.class CliqueNode20.{21.friend class Clique;22.public:23.operator int() const24.{25.return un;26.}27.private:28.int cn, //当前团的顶点数29.un, //当前团最大顶点数的上界30.level; //节点在子集空间树中所处的层次31.bbnode *ptr; //指向活节点在子集树中相应节点的指针32.};33.34.class Clique35.{36.friend int main(void);37.public:38.int BBMaxClique(int[]);39.private:40.void AddLiveNode(MaxHeap<CliqueNode>&H,int cn,int un,int level,bbnode E[],bool ch);41.int**a, //图G的邻接矩阵42.n; //图G的顶点数43.};44.45.int main()46.{47.int bestx[N+1];48.int**a = new int*[N+1];49.for(int i=1;i<=N;i++)50.{51.a[i] = new int[N+1];52.}53.54.cout<<"图G的邻接矩阵为:"<<endl;55.for(int i=1; i<=N; i++)56.{57.for(int j=1; j<=N; j++)58.{59.fin>>a[i][j];60.cout<<a[i][j]<<" ";61.}62.cout<<endl;63.}64.65.Clique c;66.= a;67.= N;68.69.cout<<"图G的最大团顶点个数为："<<(bestx)<<endl;70.cout<<"图G的最大团解向量为："<<endl;71.for(int i=1;i<=N;i++)72.{73.cout<<bestx[i]<<" ";74.}75.cout<<endl;76.77.for(int i=1;i<=N;i++)78.{79.delete[] a[i];80.}81.delete[]a;82.return0;83.}84.85.//将活节点加入到子集空间树中并插入到最大堆中86.void Clique::AddLiveNode(MaxHeap<CliqueNode> &H, int cn, int un, int level,bbnode E[], bool ch)87.{88.bbnode *b = new bbnode;89.b->parent = E;90.b->LChild = ch;91.92.CliqueNode N;93.= cn;94.= b;95.= un;96.= level;97.(N);98.}99.100.//解最大团问题的优先队列式分支限界法101.int Clique::BBMaxClique(int bestx[])102.{103.MaxHeap<CliqueNode> H(1000);104.105.//初始化106.bbnode *E = 0;107.int i = 1, = 0,109.bestn = 0;110.111.//搜集子集空间树112.while(i!=n+1)//非叶节点113.{114.//检查顶点i与当前团中其他顶点之间是否有边相连115.bool OK = true;116.bbnode *B = E;117.for(int j=i-1; j>0; B=B->parent,j--)118.{119.if(B->LChild && a[i][j]==0)120.{121.OK = false;122.break;123.}124.}125.126.if(OK)//左儿子节点为可行结点127.{128.if(cn+1>bestn)129.{130.bestn = cn + 1;131.}132.AddLiveNode(H,cn+1,cn+n-i+1,i+1,E,true); 133.}134.135.if(cn+n-i>=bestn)//右子树可能含有最优解136.{137.AddLiveNode(H,cn,cn+n-i,i+1,E,false); 138.}139.140.//取下一扩展节点141.CliqueNode N;142.(N); //堆非空143. E = ; = ;145.i = ;146.}147.148.//构造当前最优解149.for(int j=n; j>0; j--)150.{151.bestx[j] = E->LChild; 152. E = E->parent; 153.}154.155.return bestn;156.}。