基础算法与数据结构（十一） 二分图匹配

二分图匹配概述

首先是什么二分图？

有一个无向图G = (U ∪ V, E) ，所有的顶点可以划分为U，V两个不相交的顶点集，那么就是一个二分图。

二分图的最大匹配就是找到两个集合可以通过边相连且一一对应的最多对数。

如果能够得到一个所有顶点都可以一一对应，那么这个图称为完美匹配。

二分图匹配的应用

二分图匹配问题可以用来解决任务分配的问题，求得可以被分配的最多任务数目之类的问题。

二分图匹配的解法一 — 利用最大流

如何利用最大流解决这个二分图匹配？

换个想法，把所有的连接边作为一个有向图，从左边到右边的顺序建立这个流网络。设立超级源点，超级汇点，并且所有边的最大容量只有1。也就是能够得到的最大流量也就是能够通过这个网络图走到右边节点的个数。如果有匹配那么就能走通，所以就能用这个想法解决这个二分图匹配问题。

利用最大流就是这样可以解决。

匈牙利算法

利用一个匈牙利算法也可以解决这个二分图匹配的问题。

这个算法在网络上可以找到很多讲解的优秀文章，前人之述备矣，也就不再另外造轮子了。