最大团问题
class Clique {
friend int MaxClique(int**, int [], int);
private:
void Backtrack(int i);
int **a, n, *x, *bestx, cn, bestn;
};
void Clique::Backtrack(int i) {
if (i > n) {
for (int j = 1; j <= n; j++) {
bestx[j] = x[j];
}
bestn = cn;
return;
}
int ok = 1;
for (int j = 1; j < i; j++) {
if (x[j] && !a[i][j]) {
ok = 0;
break;
}
}
if (ok) {
x[i] = 1;
cn++;
Backtrack(i + 1);
x[i] = 0;
cn--;
}
if (cn + n - i > bestn) {
x[i] = 0;
Backtrack(i + 1);
}
}
int MaxClique(int **a, int v[], int n) {
Clique Y;
Y.x = new int[n + 1];
Y.a = a;
Y.n = n;
Y.cn = 0;
Y.bestn = 0;
Y.bestx = v;
Y.Backtrack(1);
delete [] Y.x;
return Y.bestn;
}
最后更新:
2024年1月14日 18:59:58
创建日期: 2024年1月2日 19:47:42
创建日期: 2024年1月2日 19:47:42