匈牙利算法

发表于 2020-03-22 更新于 2020-11-06 分类于计算机科学阅读次数： Valine：

本文字数： 2.1k 阅读时长 ≈ 2 分钟

匈牙利算法

毕设里的一个子问题是求解二分图最大权匹配，网上搜了不少资料最终决定使用KM算法。KM算法的基础是求解二分图最大匹配的匈牙利算法，现在来整理一下这几天所学。

基础概念

二分图：如果把一个图的顶点集划分成两个不相交集\(X\)和\(Y\)，使得图里的每一条边都分别连接\(X\)和\(Y\)里的顶点，这样的图就叫做二分图。
匹配：图的匹配是边集的一个子集，里面的任意两条边都没有公共的顶点。
最大匹配：在一个图的所有匹配里，边数最多的匹配称为最大匹配。
完备匹配和完美匹配：如果一个图的某个匹配里，被划分的两个点集\(X\)和\(Y\)中有一个点集里的所有点都是匹配点，就称这个匹配是完备匹配。如果两个点集里都是匹配点，就称这个匹配是完美匹配。
交替路：从一个未匹配点出发，经过匹配点、未匹配点、匹配点如此重复下去形成的一条路径，称为交替路。
增广路：起点终点都是未匹配点的交替路称为增广路。

增广路

增广路一定由奇数条边组成
增广路中未匹配边一定比匹配边多一条

这两条结论非常显然：增广路的两端都是未匹配点，两端的第一段路径都是未匹配边，中间又必须是匹配边和未匹配边重复偶数次。

仔细思考这两条结论就会发现：增广路通过一次“取反”操作（让匹配边和未匹配边的身份调换）就能让匹配边数+1。

算法的思路

有了上面的观察，就能够利用这个思想设计出求解最大匹配的算法了：

从\(X\)中取一个未匹配点\(x_1\)，然后在\(Y\)里取一个与之相连的点\(y_1\)，如果\(y_1\)还未被匹配，那直接匹配就行了；

如果\(y_1\)已经被匹配了，接下来的两种策略分别对应了DFS和BFS

不放过\(y_1\)，回到\(X\)里找到和它匹配的点\(x_2\)，直接强迫\(x_2\)另寻匹配点，把\(y_1\)让出来给\(x_1\)
放过\(y_1\)，在\(Y\)里找下一个和它相连的点\(y_2\)，看能否匹配，直到\(Y\)里真的没有能匹配的点了，才强迫\(x_2\)另寻匹配点，\(x_1\)自己匹配\(y_1\)

那这跟增广路有什么关系呢？仔细推敲一下就能领悟其中的奥秘所在。增广路的“取反”操作与算法里的“强迫另寻匹配点”正是对应着的。换言之，\(x_1\)找到了一个未匹配点，或者从\(x_1\)找到了一条增广路，都能够使匹配边数+1.

算法的实现

（最近手生且毕设DDL迫在眉睫，BFS版本暂时先鸽一下~）

DFS版本

为简单起见就直接用邻接矩阵来存储图

int Graph[maxm][maxn]; // 邻接矩阵存储图
int match[maxn]; // 记录匹配
bool inCrossPath[maxn]; // 工作数组：记录该点是否已经在交错路里
int ans; // 最大匹配数
void addEdge(int u, int v)
{
    Graph[u][v] = 1; // 越界啥的先不管了
}

下面是核心的DFS代码

bool findPath(int u) // 为集合X里的结点u寻找匹配点
{
    for (int i = 1; i <= maxn; i++)
    {
        if (Graph[u][i] == 1 && inCrossPath[i] == false) // Y里的结点i与u相连，而且i在本次匹配中还未在交错路里
        {
            inCrossPath[i] = true; // 记录i已经在交错路里
            if (match[i] == -1 || findPath(match[i])) // 如果i未被匹配，或者i的前任匹配点能另外找到匹配点，就让u和i匹配
            {
                match[i] = u;
                return true;
            }
        }
    }
    return false;
}

然后是匈牙利算法的代码

void Hungary()
{
    for (int i = 1; i <= m; i++) // 让X里每个点都寻找匹配点
    {
        memset(inCrossPath, false, sizeof(inCrossPath)); // 每次都要把工作数组清空
        if (findPath(i))
            ans++; // 无论是直接连，还是通过DFS找到增广路径然后求反，最终结果都是匹配数+1
    }
}