最大团问题
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;
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.ptr = b;
N.un = un;
N.level = level;
H.Insert(N);
}
int Clique::BBMaxClique(int bestx[]) {
MaxHeap<CliqueNode> H(1000);
bbnode *E = 0;
int i = 0, 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, cn + n - i, i + 1, E, false);
}
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;
}
最后更新:
2024年1月14日 20:14:02
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42