思路

解空间: 子集树

约束条件: 当前节点是否能够和所有的已选节点可达

对于每一个节点，左子树表示选择该节点，右子树表示不选择；使用变量 currNum 记录已经选取的节点数

采用 根-左-右 的遍历方法，即优先考虑选取该节点，后考虑不选取该节点两种情况

• 若到达底部时，若当先选择的节点数大于最大节点数，则替换

• 若未到达底部，因为该结点无法继续选取，先判断取右子树：假如选取剩余所有节点是否能超过最大节点数

  • 若不能则回溯至上一节点，并再次进行判断**(剪枝)**

  • 若能，意味着该节点的右子树仍有可尝试的价值，则取该节点的右子树，到达下一层后从选取左子树开始循环

实现代码

public static void main(String[] args) {
    int max = Integer.MAX_VALUE;
    int[][] graph = {{},
            {max, 1, 1, 0, 1, 1},
            {max, 1, 1, 1, 0, 1},
            {max, 0, 1, 1, 0, 1},
            {max, 1, 0, 0, 1, 1},
            {max, 1, 2, 3, 0, 1}};
    int n = 5;

    maxClique(graph, n);
}

public static void maxClique(int[][] graph, int n) {
    boolean[] isInclude = new boolean[n + 1];
    boolean[] maxC = new boolean[n + 1];
    int maxNum = 0; // 最大的节点数
    int currNum = 0; // 当前已取的节点数

    int i = 1;
    while (true) {
        // 左表示取该点,右表示不取
        // 未到达底部, 且当前节点可取
        // 进入左子树
        while (i <= n && isIncludeAble(isInclude, graph, i)) {
            isInclude[i] = true;
            currNum++;
            i++;
        }
        // 到达底部
        if (i > n) {
            if (currNum > maxNum) {
                maxNum = currNum;
                for (int j = 1; j <= n; ++j) {
                    maxC[j] = isInclude[j];
                }
            }
        } else {
            // 未到达底部
            i++;
        }
        // 若剩余的节点加上已选节点不能大于最大节点数,回溯
        while (currNum + n - i <= maxNum) {
            i--;
            // 如果当前位置为右子数
            while (i > 0 && !isInclude[i]) {
                i--;
            }
            // 当从根节点的右子树回溯完成
            if (i == 0) {
                System.out.println("最大团为");
                for (int j = 1; j <= n; ++j) {
                    if (maxC[j]) {
                        System.out.print(j + " ");
                    }
                }
                return;
            }
            // 从左子树回溯完成后进入右子树
            isInclude[i] = false;
            currNum--;
            i++;
        }
    }
}

public static boolean isIncludeAble(boolean[] isInclude, int[][] graph, int i) {
    for (int j = 1; j < isInclude.length; ++j) {
        // 若对于已取的节点与将要取的节点 i 不可达
        if (isInclude[j] && graph[j][i] != 1) {
            return false;
        }
    }
    return true;
}