一、问题描述

设一个无向图G ( V , E ) G(V,E)G(V,E)，V VV为点集，E EE为两点间的边集。设U UU为V VV的一个子集，若对于任意的结点对u uu,v vv属于U UU都有边连通，则称点集U构成的图为 完全子图 。无向图G GG的完全子图U UU是G GG的团，G GG的最大团即为G GG的最大完全子图。

二、解决思路

可以将节点选择加入和不加入当期那的子图，加入和不加入分别是两种道路，并且节点的加入不加入没有优先级，所以这里可以先排列节点的选择顺序，因为顺序不影响最终的结果，使用临接矩阵存储节点之间的边的关系。其中限界函数查找临接矩阵中是否存在边，不存在则代表当前节点只能走不加入的道路，然后向下递归不加入的道路。剪枝函数可以设定为判定如果走不加入的道路剩余的节点是否大于当前最优值，也就最优解产生的可能性，可能性为0则不走当前的道路。具体搜索过程如下

最大团.png

三、代码

public class MaximumGroup {
    public static void main(String[] args) {
        //邻接矩阵存储图 0代表相连否则不相连
        int[][] adjacencyMatrix = new int[][]{
                {0, 1, 1, 1, 1},
                {1, 0, 1, 0, 0},
                {1, 1, 0, 1, 1},
                {1, 0, 1, 0, 1},
                {1, 0, 1, 1, 0}};
        //保存当前的节点加入状态
        int[] currentStatus = new int[adjacencyMatrix.length];
        //保存最好结果的节点加入状态
        int[] bestStatus = new int[adjacencyMatrix.length];
        //代表最好结果的人数
        int bestValue = maxCompletelyGroup(adjacencyMatrix, 0, currentStatus, bestStatus, 0, 0);
        System.out.println(bestValue);
        System.out.println(Arrays.toString(bestStatus));


    }

    public static Integer maxCompletelyGroup(int[][] adjacencyMatrix, int i, int[] currentStatus, int[] bestStatus, int bestVale, int currentValue) {

        /**
         * 递归的终点，最优解一定是到达叶子节点的
         */
        if (i > adjacencyMatrix.length - 1) {
            //记录最优解
            for (int j = 0; j < adjacencyMatrix.length; j++) {
                bestStatus[j] = currentStatus[j];
            }
            bestVale = currentValue;
            return bestVale;
        }


        /**
         * 节点判断阶段，如果满足加入条件则加入，递归下个节点，拿到最优值后进行回溯，选择不加入这个节点
         */
        if (isAccordWithJoin(adjacencyMatrix, i, currentStatus)) {
            //代表可以加入
            currentStatus[i] = 1;
            //当前值加一
            currentValue += 1;

            //向下递归节点
            bestVale = maxCompletelyGroup(adjacencyMatrix, i + 1, currentStatus, bestStatus, bestVale, currentValue);

            //将当前节点回溯走下面的判断
            currentValue -= 1;
        }

        /**
         * 减枝函数 进行粗略判断下面的能否加入
         * 假设剩下的节点都能加入，则判断和当前最优值的大小，否则则没必要向下扩展
         */
        if ((currentValue + adjacencyMatrix.length - i - 1) > bestVale) {
            //表示当前节点走不加入的道路，递归计算不加入情况下剩余节点和已加入节点的值
            currentStatus[i] = 0;
            bestVale = maxCompletelyGroup(adjacencyMatrix, i + 1, currentStatus, bestStatus, bestVale, currentValue);
        }


        return bestVale;
    }

    /**
     * 限界条件
     * 判断当前节点是否能够加入
     * 循环截止到当前顶点，如果有不相连的则不能加入
     *
     * @param adjancencyMatrix
     * @param i
     * @param currentStatus
     * @return
     */
    public static boolean isAccordWithJoin(int[][] adjancencyMatrix, int i, int[] currentStatus) {
        for (int j = 0; j < i; j++) {
            //判断当前节点如果在子图中则判断是否和i有边，没有false
            if (currentStatus[j] == 1) {
                if (adjancencyMatrix[j][i] == 0) {
                    return false;
                }
            }
        }
        return true;
    }
}

四、优化空间