MENU

最大团问题

November 7, 2018 • Read: 290 • 算法

最大团

给定无向图G=(V,E),其中V是非空集合,称为顶点集;E是V中元素构成的无序二元组的集合,称为边集,无向图中的边均是定点的无序对,无序对常用圆括号“()”表示。

普及几个概念:

  • 无向图:边没有方向。如果点A和B之间有一条边,那么既可以从A到B,也可以从B到A
  • 完全图:任意两点之间都有边相连。假设一个图有$n$个点,那么就应该有$\frac{n\times(n-1)}{2}$条边
  • 子图:选取原图中的部分结点,以及与该点相连的所有边,构建出的新图

了解上面几个概念以后,给出最大团的定义:在一个无向图中找出一个点数最多的完全子图

DFS求最大团


假设现在有这么一个图,我们用肉眼看一下就知道他的最大团数是3,(1,2,5),(1,4,5),(2,3,5)都是最大团

DFS求最大团的主要思路是构建一棵二叉子集树,每次枚举添加或不添加当前结点到当前已经构建好的团中,如下图,0就是不添加,1就是添加

这样枚举的话时间复杂度是$O(2^n)$,考虑能不能剪枝,答案当然是可以的

首先思考一下,什么情况下,枚举到的这个结点可以选?假设DFS执行下来我已经选了1和2,那么3选还是不选?肯定不选,因为如果选了就无法与1和2构成完全图

假设我在搜索过程中已经得到了一个解bestn,如果剩下的所有点加上我当前已选的点,都不够超过bestn,那我就没必要往后枚举了。这个说起来可能比较抽象,举个例子,一共5个点,bestn已经更新成了3,当前树的路径是{1,0}(对应的选择就是1选,2不选),假设现在枚举3不选,那么还剩下两个点4,5,不管4,5能不能与我当前的团构成完全图,我就假设4,5都选上,那么我最大团的结点数为3,根本没有超过bestn,都无法得到更好的答案,我干嘛要枚举呢,所以3不选的这棵子树直接砍了

代码

import java.util.Scanner;

public class Main {
    static int[][] map;//邻接矩阵保存图
    static int[] book;//记录每个点选还是不选
    static int bestn = Integer.MIN_VALUE;
    static int n,m;//n个点,m条边
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        n = cin.nextInt();
        m = cin.nextInt();
        map = new int[n + 1][n + 1];
        book = new int[n + 1];
        for(int i = 0;i < m;i++) {
            int a = cin.nextInt();
            int b = cin.nextInt();
            map[a][b] = 1;
            map[b][a] = 1;
        }
        dfs(1,0);
        System.out.println(bestn);
    }
    static void dfs(int idx,int num) {//第idx个点,当前选了num个点
        if(idx == n + 1) {
            bestn = Math.max(bestn,num);
            return;
        }
        for(int i = 0;i < 2;i++) {//二叉树
            if(i == 0) {//不选
                if(num + n - idx > bestn) 
                    dfs(idx + 1,num);
            } else { //选
                if(check(idx)) {
                    book[idx] = 1;
                    dfs(idx + 1,num + 1);
                    book[idx] = 0;
                }
            }
        }
    }
    static boolean check(int idx) {
        for(int i = 1;i < idx;i++) 
            if(book[i] == 1 && map[i][idx] != 1)
                return false;
        return true;
    }
}
/*
输入:
5 7
1 2
2 3
5 3
4 5
1 4
1 5
2 5
输出:
3
*/

HDU1530

题意:给定N个点的无向图,让你求最大团
Java tle了,不知道为什么

import java.util.Scanner;

public class Main {
    static int[][] map;
    static int[] book;
    static int bestn;
    static int n;

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (true) {
            bestn = Integer.MIN_VALUE;
            n = cin.nextInt();
            if(n == 0)
                break;
            map = new int[n + 1][n + 1];
            book = new int[n + 1];
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    int flag = cin.nextInt();
                    map[i][j] = flag;
                }
            }
            dfs(1, 0);
            System.out.println(bestn);
        }
    }

    static void dfs(int idx, int num) {
        if (idx == n + 1) {
            bestn = Math.max(bestn, num);
            return;
        }
        for (int i = 0; i < 2; i++) {
            if (i == 0) {
                if (num + n - idx > bestn)
                    dfs(idx + 1, num);
            } else { 
                if (check(idx)) {
                    book[idx] = 1;
                    dfs(idx + 1, num + 1);
                    book[idx] = 0;
                }
            }
        }
    }

    static boolean check(int idx) {
        for (int i = 1; i < idx; i++)
            if (book[i] == 1 && map[i][idx] != 1)
                return false;
        return true;
    }
}
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment