网易笔试（2020-9-12）配对问题 匈牙利算法

算法 网易笔试（2020-9-12）配对问题

@author:Jingdai

@date:2020.09.14

前几天看到一个网易算法题，不会做，看了博客和书，现在总结一下，方便以后看。

题目描述

相亲活动，男生可以选一个或几个有意向的女生，女生同样；如果互相有意向，则可以初步配对成功，一个男生只能和一个女生配对，问最大的匹配数。

示例:

三个男生1,2,3

三个女生1,2,3

最初6个配对（左男右女）：

1-1 1-2 2-1 2-2 3-3 3-2

则最大匹配数就是3。

理论知识

查阅相关资料，这是一个标准的二分图的最大匹配问题，有一个专门的解法匈牙利算法。因为我也是图论小白，所以我以自己通俗的理解来说明几个概念。

• 二分图

  无向图 G=(V,E)，若顶点集 V 可以分成两个子集A，B，且A∩B=∅，A∪B=V，且边集 E 中的每一条边的两个顶点都分别属于 A 和 B ，则图 G 称为二分图。如下图就是一个二分图。

  

• 匹配

  对于二分图，边集 E 的某一个子集 M，如果 M 中的每条边都不相交，则称为二分图的一个匹配。M 中 边的条数称为匹配数，图中红色的边就是一个匹配。

• 最大匹配

  顾名思义，就是一个图中匹配数最大的匹配就是最大匹配。

• 可增广路

  这个比前面的稍微复杂一点点。如果 p 是图 G 中连接两个未匹配点（分别属于子集A和B，如5和3）的路径，且 p 中属于匹配边集 M 和不属于匹配边集（E-M）交替出现，则 p 是一个相对于 M 的可增广路。看下面图的例子理解。

图中红色的边代表匹配，路径（5-1-4-3）就是一条增广路径。

注意，只包含两个未匹配点的路径也是一条增广路径，即图中路径（2-5）也是一个增广路径。

• 匈牙利算法

  懂了怎么找可增广路之后，就可以看这个算法了。先看以下几个性质：

  • 可增广路 p 经过取反后一定可以得到一个更大的匹配 M‘

    还是看图解释，
    

    对于可增广路（5-1-4-3），原来属于匹配边集的是（1-4） ，不属于匹配边集的是（5-1）、（4-3）；现在取反，得到属于匹配边集的是（5-1）、（4-3），不属于匹配边集的（1-4），匹配数从1变成了2。

  • （Berge匹配定理）M是图G 的最大匹配，当且仅当G中不存在M的增广路。（对证明有兴趣的童靴可以去看图论）

  其实简单的说，匈牙利算法就是不断的找图的可增广路，然后取反增大匹配数，当找不到可增广路时就可以说明找到了最大匹配数。

代码

下面介绍代码。

import java.util.*;

public class PairSolution {

    public static void main(String[] args){

        Scanner s = new Scanner(System.in);
        
        // boys and girls number
        String tempLine = s.nextLine();
        String[] mn = tempLine.split(" ");
        int m = Integer.valueOf(mn[0]);
        int n = Integer.valueOf(mn[1]);

        // pre pair number
        tempLine = s.nextLine();
        int prePairCount = Integer.valueOf(tempLine);

        // link matrix
        boolean[][] linkMatrix = new boolean[m+1][n+1];
        for (int i = 0; i < prePairCount; i++) {
            tempLine = s.nextLine();
            String[] xy = tempLine.split(" ");
            int x = Integer.valueOf(xy[0]);
            int y = Integer.valueOf(xy[1]);
            linkMatrix[x][y] = true;
        }
        
        System.out.println(solution(linkMatrix, m, n));

    }

    public static int solution(boolean[][] linkMatrix, int m, int n) {
        
        int pairCount = 0;
        int[] paired = new int[n+1];
        for (int i = 1; i <= m; i++) {
            boolean[] visited = new boolean[n+1];
            if (pair(i, visited, paired, linkMatrix)) {
                pairCount ++;
            }
        }
        return pairCount;

    }

    private static boolean pair(int m, boolean[] visited, int[] paired, boolean[][] linkMatrix) {

        int n = linkMatrix[0].length - 1;
        for (int j = 1; j <= n; j++) {
            if (linkMatrix[m][j] && !visited[j]) {
                visited[j] = true;
                if (paired[j] == 0) {
                    paired[j] = m;
                    return true;
                } else if (pair(paired[j], visited, paired, linkMatrix)) {
                    paired[j] = m;
                    return true;
                }
            }
        }
        return false;

    }

}

代码解析

代码中，main 函数就是接收输入。

• 第一行为男生女生人数，空格分隔。
• 第二行表示初试配对数
• 后面各行代表配对关系

如上面的输入代表有3男3女，初始有6个匹配，后面是每个具体匹配关系。

然后是solution 方法，这个方法也很好理解，对于每个男生，如果可以通过 pair 方法找到一个配对，就使匹配数加一。

• pair 方法

  这个是核心方法，对第 m 个男生进行配对，遍历 n 个女生。

  • 对于每个女生，如果该女生还没有配对，则直接使她与第 m 个男生配对，（这里就相当于找到了一个只包含两个未匹配点的增广路径），使匹配数增加1。

  • 如果该女生已经配对了，则试图使她以前配对的男生重新进行配对，给当前的第 m 个男生让出位置，如果成功，则代表可以让位，则也使匹配数加一。（这里相当于找从 m 号男生出发的增广路径，可以让位代表找到，否则代表没有找到，看后面图。）

  • 这里可能有一个疑惑点就是为什么对于每个男生，都需要有一个 visited 数组，我开始疑惑了好久，下面我画图解释一下。

  

  如图所示，现在已经有两个匹配（1-4）和 （3-5），现对 2 号进行 pair 方法查找，首先找到4号, 4号已经和1号配对，则对1号进行配对，这里已经递归了，对1号进行了pair 方法查找，1 号找到5号，发现5号也已经和3 号配对，则再次递归对 3 号进行pair方法查找，这里如果没有对5号进行标记visited就会一直对3号进行pair方法查找。所以必须加visited数组标记，同时，最重要的是，刚才将4 , 5号标记为visited，如果没有标记，你会在for循环中再次尝试 2 号和 5 号配对，但是这里肯定是找不到增广路径的，因为你会发现（2-4-1-5-xxxx）和（2-5-xxxx）后面是相同的，如果可以找到增广路径，则在上一轮就找到了，就返回了，不会到这里，所以也不用再浪费时间在去尝试 5 号了，即需要一个 visited 数组。

  • 总结，如果自己走一遍流程会发现其实过程很有意思。

    其实整个过程就是从左边找一个未匹配点，如果右边有直接相连的未匹配点，则直接找到；否则先经过一个未匹配边，在经过一个匹配边回到左边（如 2 经过(2-4-1)回到1）。在对现在的点（这里是1 ）继续该过程，如果有直接相连的未匹配点，找到返回，否则继续。。。这就是一个递归的过程。如果最后找到右边的未匹配点，则代表可以使匹配数加一，其实整个路径就是一个增广路径，你自己走一遍就会发现。