算法笔记【6】匈牙利算法

一时失言乱红尘 2023-01-11 01:25 128阅读 0赞

# 算法笔记【6】 匈牙利算法 #

## 匈牙利算法简介 ##

**今天我们来看一个没有前几篇讲的那么常用，但是很有用的算法：匈牙利算法（Hungarian algorithm）。匈牙利算法主要用于解决一些与**二分图匹配\*\*有关的问题，所以我们先来了解一下二分图。

**二分图**（**Bipartite graph**）是一类特殊的**图**，它可以被划分为两个部分，每个部分内的点互不相连。下图是典型的二分图。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]

可以看到，在上面的二分图中，每条边的端点都分别处于点集X和Y中。匈牙利算法主要用来解决两个问题：求二分图的**最大匹配数**和**最小点覆盖数**。

这么说起来过于抽象了，我们现在从实际问题出发。

## 最大匹配问题 ##

看完上面讲的，相信读者会觉得云里雾里的：这是啥？这有啥用？所以我们把这张二分图稍微做点手脚，变成下面这样：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 1]

现在Boys和Girls分别是两个点集，里面的点分别是男生和女生，边表示他们之间存在“暧昧关系"。最大匹配问题相当于，**假如你是红娘，可以撮合任何一对有暧昧关系的男女，那么你最多能成全多少对情侣**？（数学表述：在二分图中最多能找到多少条没有公共端点的边）

现在我们来看看匈牙利算法是怎么运作的：

我们从B1看起（男女平等，从女生这边看起也是可以的），他与G2有暧昧，那我们就先暂时把他与G2连接（注意这时只是你作为一个红娘在纸上构想，你没有真正行动，此时的安排都是暂时的）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 2]

来看B2，B2也喜欢G2，这时G2已经“名花有主”了（虽然只是我们设想的），那怎么办呢？我们倒回去看G2目前被安排的男友，是B1，B1有没有别的选项呢？有，G4，G4还没有被安排，那我们就给B1安排上G4。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 3]

然后B3，B3直接配上G1就好了，这没什么问题。至于B4，他只钟情于G4，G4目前配的是B1。B1除了G4还可以选G2，但是呢，如果B1选了G2，G2的原配B2就没得选了。我们绕了一大圈，发现B4只能注定单身了，可怜。（其实从来没被考虑过的G3更可怜）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 4]

这就是匈牙利算法的流程，至于具体实现，我们来看看代码：

public class Arithmetic6 { 
        public static void main(String[] args) { 
            int[][] map = new int[][]{ { 1, 1, 0, 1, 0, 0, 0},
                    { 0, 1, 0, 0, 1, 0, 0},
                    { 1, 0, 0, 1, 0, 0, 1},
                    { 0, 0, 1, 1, 0, 1, 0},
                    { 0, 0, 0, 1, 0, 0, 0},
                    { 0, 0, 0, 1, 0, 0, 0}};
            Hungarian hungarian = new Hungarian(map);
            int hungarian1 = hungarian.hungarian();
            System.out.println(hungarian1);
        }
    
        static class Hungarian { 
            int m, n;//M, N分别表示左、右侧集合的元素数量
            int[][] map;//邻接矩阵存图
            int[] p;//记录当前右侧元素所对应的左侧元素
            boolean[] vis;//记录右侧元素是否已被访问过
    
            public Hungarian(int[][] map) { 
                this.m = map.length;
                this.n = map[0].length;
                this.map = map;
                this.p = new int[n];
                this.vis = new boolean[n];
    
            }
    
            boolean match(int i, int b) { 
                for (int j = b; j < n; j++) { 
                    if (map[i][j] != 0) { 
                        // 右侧第j号被匹配过了 递归去找 匹配 p[j] 的对象 有没有其他可以匹配的
                        if (vis[j]) { 
                            if (match(p[j], j + 1)) { 
                                p[j] = i;
                                return true;
                            }
                        } else { 
                            //没有匹配 直接配对
                            vis[j] = true;
                            p[j] = i;
                            return true;
                        }
                    }
                }
                return false;
            }
    
            public int hungarian() { 
                int cnt = 0;
                for (int i = 0; i < m; ++i) { 
                    if (match(i, 0)) { 
                        cnt++;
                    }
                }
                return cnt;
            }
    
        }
    }

其实流程跟我们上面描述的是一致的。注意这里使用了一个递归的技巧，我们不断往下递归，尝试寻找合适的匹配。

## 最小点覆盖问题 ##

另外一个关于二分图的问题是求**最小点覆盖**：我们想找到**最少**的一些**点**，使二分图所有的边都**至少有一个端点**在这些点之中。倒过来说就是，删除包含这些点的边，可以删掉所有边。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 5]

这为什么用匈牙利算法可以解决呢？你如果以为我要长篇大论很久就错了，我们只需要一个定理：

**（König定理）**

> 一个二分图中的最大匹配数**等于**这个图中的最小点覆盖数

好了，本节可以结束了，我们不是搞数学的，不需要证明（有兴趣的话可以参考[这篇博客][Link 1]，虽然愚昧的我并没看懂）。但是提供一个直观地找最小覆盖点集的方法：看上节最后一张图（或题图），从左侧一个**未匹配成功的点**出发，走一趟匈牙利算法的流程（即紫色的箭头），所有**左侧未经过的点**，和**右侧经过的点**，即组成最小点覆盖。（即图中的B3、G2、G4）

\--------------最后感谢大家的阅读，愿大家技术越来越流弊！--------------

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]

\--------------也希望大家给我点支持，谢谢各位大佬了！！！--------------

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center]: /images/20221119/7d3454264b724ac9b49d84f7cb915630.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210125182109407.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210125182100276.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210125182052982.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 4]: https://img-blog.csdnimg.cn/20210125182043675.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70_pic_center 5]: https://img-blog.csdnimg.cn/2021012518203285.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70#pic_center
[Link 1]: https://link.zhihu.com/?target=http%3A//www.matrix67.com/blog/archives/116
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200721144257696.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1phY2tfdHpo,size_16,color_FFFFFF,t_70