欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-14 14:38:16
...

算法 网易笔试(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 称为二分图。如下图就是一个二分图。

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

  • 匹配

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

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

  • 最大匹配

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

  • 可增广路

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

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

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

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

  • 匈牙利算法

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

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

      还是看图解释,
      网易笔试(2020-9-12)配对问题 匈牙利算法

      对于可增广路(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 函数就是接收输入。

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

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

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

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

  • pair 方法

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

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

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

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

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

    如图所示,现在已经有两个匹配(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 )继续该过程,如果有直接相连的未匹配点,找到返回,否则继续。。。这就是一个递归的过程。如果最后找到右边的未匹配点,则代表可以使匹配数加一,其实整个路径就是一个增广路径,你自己走一遍就会发现。

相关标签: 算法 面试