问题描述:
给定无向图G=(V, E),其中V是非空集合,称为顶点集;
E是V中元素构成的无序二元组的集合,称为边集,无向图中的边均是顶点的无序对,无序对常用圆括号“( )”表示。
如果U∈V,且对任意两个顶点u,v∈U有(u, v)∈E,则称U是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'的最大独立集。
问题定义:
解空间树中结点类型:bbnode
活结点优先队列中元素类型为 CliqueNode(cn 表示与该节点相应的团的定点数,un表示结点为根的子树中的最大顶点树的上界。level表示结点在子集空间树中所处的层次;ch 左右儿子的结点标记)
ch=1 左儿子 ch=0 右儿子
ptr 指向解空间树中相应结点的指针
cn+n-level+1表示定点数上界的un值。
代码描述:
相关结构体定义:
class bbnode{
friend class Clique;
private:
bbnode * parent;
bool LChild;
};
class CliqueNode{
friend class Clique;
public:
operator int () const {return un;}
private:
int cn,
un,
level;
bbnode *ptr;
};
class Clique{
friend void main(void);
public:
int BBMaxClique(int []);
private:
void AddLiveNode(MaxHeap<CliqueNode> &H,int cn,int un,int level,bbnode E[],bool ch);
int * * a ,n;
};
AddLiveNode:将当前构造的活结点 加入到子集空间树中并插入活结点优先队列中。
void Clique::AddLiveNode(MaxHeap<CliqueNode> &H,int cn,int un,int level,bbnode E[],bool ch)
{
bbnode * b = new bbnode;
b->parent = E;
b->LChild = ch;
CliqueNode N;
N.cn = cn;
N.level = level;
N.un = un;
N.Insert(N);
}
算法核心代码:BBMaxClique
子集树的根节点是 初始扩展结点 cn为0
i 表示当前扩展结点的解空间树中所处的层次。
首先考察左儿子:
顶点加入当前团,检查该顶点与当前团中其他顶点是否有边相连。
都有边,可行,纳入 活结点 优先队列中,AddLiveNode(),接着考察当前扩展结点的 右儿子结点,仅当un>bestn时,右子树中可能含有最优解 ;
否则,不可行。
int Clique::BBMaxClique(int bestx[])
{
MaxHeap<CliqueNode> H(1000);
bbnode * E = 0;
int i=1,
cn = 0,
bestn = 0;
while(i != n+1)
{
bool OK = true;
bbnode * B = E;
for(int j = i-1;j>0;B=B->parent,j--)
{
if(B->LChild && a[i][j]==0)
{
OK = false;
break;
}
}
if(OK)
{
if(cn + 1 > bestn)
bestn = cn + 1;
AddLiveNode(H,cn+1,cn+n-i+1,i+1,E,true);
}
if(cn+n-i >= bestn)
AddLiveNode(H,cn+1,cn+n-i+1,i+1,E,true);
CliqueNode N;
H.DeleteMax(N);
E = N.ptr;
cn = N.cn;
i = N.level;
}
for(int j=n;j>0;j--)
{
bestx[j] = E->LChild;
E = E->parent;
}
return bestn;
}