二分图(二部图)判别和最大匹配问题(匈牙利算法)

二分图(二部图)

如何判断一个图是否是二分图,二分图就是可以将图分为两个部分,边都是在两个部分之间,而每个部分内部不可以有边相连。

这样如果二部图中存在一个环,那么这个环中的边数必须是偶数,可以画图验证一下三角形、四边形和五边形就知道了。

那么环中的边数是偶数,就可以利用染色算法来进行判别,环是偶数则两种颜色可以交替,否则必定有两个相邻的节点颜色相同。

可以利用BFS算法(结合队列)对二分图进行判别。关键代码如下:

输入:

7
1 4
1 5
1 6
2 5
3 5
3 6
3 4
2 6
 public static void main(String[] args) throws Exception{
       
        Scanner sc = new Scanner(System.in);
        //读入数据,并构建邻接表
        int n = sc.nextInt();
        int [] colors = new int[n];
        HashMap <Integer, ArrayList<Integer>> hm = new HashMap<>();
        for (int i = 0; i < n; i++) {
            hm.put(i, new ArrayList<>());
        }
        while (sc.hasNext()) {
            int forward = sc.nextInt();
            int backward = sc.nextInt();
            hm.get(forward).add(backward);
            hm.get(backward).add(forward);
        }
        System.out.println(hm);
        //这里节点的标识与数组的下表一一对应,也是为了简化问题,如果不是一一对应的情况,可能还需要做一次 index -> node 的转换

        for (int i = 0; i < n; i++) {
            int color = colors[i];
            if (color == 0) {
                boolean valid = BFS(hm, colors, i);
                if (!valid) {
                    System.out.println("not valid");
                    System.out.println(Arrays.toString(colors));
                    return;
                }
            }
        }
        System.out.println("valid!");
        System.out.println(Arrays.toString(colors));
    }

    public static boolean BFS(HashMap<Integer, ArrayList<Integer>> hm, int [] colors, int node) {
        LinkedList<Integer> queue = new LinkedList<>();
        colors[node] = 1;
        queue.offerLast(node);
        while(queue.size() != 0) {
            int curNode = queue.pollFirst();
            for (int neighber : hm.get(curNode)) {
                if (colors[neighber] == 0) {
                    colors[neighber] = - colors[curNode];
                    queue.offerLast(neighber);
                } else if (colors[neighber] == colors[curNode]){
                    return false;
                }
            }
        }
        return true;
    }

二分图中一个很重要的问题就是最大匹配问题,最大匹配问题利用匈牙利算法进行求解。

输入:

8
1 1
1 2
2 2
2 3
3 1
3 2
4 3
4 4

关键代码如下:

    static int maxn = 100;
    //通过邻接矩阵进行图构建
    static int [][] matrix = new int[maxn][maxn];
    static boolean [] used = new boolean[maxn]; //表示某个轮次中女生是否被匹配过,每轮都初始化
    static int [] nxt = new int[maxn];  //表示整个过程中与女生匹配的男生id ,nxt[1]=2, 表示女1和男2匹配
    static int n = 5;  //表示男生数量为4(数值多1是为了和输入的id从1开始相匹配)
    static int m = 5;  //表示女生数量为4
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        //构建邻接矩阵
        int k = sc.nextInt();
        for (int i = 0; i < k; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            matrix[a][b] = 1;
        }
        
        //开始遍历每个男生,尝试为每个男生匹配女生
        int res = 0;
        for (int i = 1; i <= n; i++) {
            //每轮都要初始化女生是否匹配数组,因为dfs(递归)找增广路的时候需要标识来调整策略
            used = new boolean[m];
            if (DFS(i)) res ++;
        }
        System.out.println(res);
    }
    
    //这个方法是匈牙利算法的核心,函数标识在当前情况下,是否(返回值)能为男x成功匹配到女生。该函数还会修改每次初始化的used数组和nxt全局数组。
    public static boolean DFS(int x) {
        //遍历每个女生看看能不能和男生x匹配上
        for (int i = 1; i <= m; i++) {
            // 如果该女生和男生x存在可匹配的边,并且女生在这一轮没有匹配过
            if (matrix[x][i] == 1 && !used[i]) {
                //标识此轮中该女生被从尝试匹配过,防止递归找增广路的时候重复访问(增广路不是环,因此不能重复访问)
                
                used[i] = true;
                //如果这次循环没有找到,会对其他轮次的循环造成影响吗,因为你修改了used数组
                //不会,因为如果存在一条增广路,经过了上次不成立的增广路,那么上次的也是一条增广路,产生矛盾。

                //如果当前女生没有匹配的男生 || 当前女生有匹配的男生,并且可以让那个匹配的男生去找一个新的女生
                if (nxt[i] == 0 || DFS(nxt[i])) {

                    nxt[i] = x;
                    return true;
                }
            }
        }
        return false;
    }

单单看代码注释还是很难理解,可能过一阵子就忘了,结合代码单个步骤调试会更加形象,后面有空整一个视频讲解吧。

参考文献