2

匈牙利算法 | Safe House

 2 years ago
source link: https://piggerzzm.github.io/2020/03/22/Hungary/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

匈牙利算法

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

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

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

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

算法的思路

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

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

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

  1. 不放过 y1，回到 X 里找到和它匹配的点 x2，直接强迫 x2 另寻匹配点，把 y1 让出来给 x1
  2. 放过 y1，在 Y 里找下一个和它相连的点 y2，看能否匹配，直到 Y 里真的没有能匹配的点了，才强迫 x2 另寻匹配点 ，x1 自己匹配 y1

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

运行 Hungary 函数之后就能够求出最大匹配数，存储在 match 数组里的最后结果正是匹配的结果。

算法正确性

（这里也暂时鸽一下）

看了不少博客，这里列出几个我认为讲解的比较好的，感谢各位大神

https://www.cnblogs.com/zpfbuaa/p/7218607.html#_label1

https://www.cnblogs.com/shenben/p/5573788.html

https://blog.csdn.net/zxn0803/article/details/49995973

https://blog.csdn.net/sixdaycoder/article/details/47680831


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK