最大团问题

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
回到页面顶部