学习笔记 匈牙利算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了学习笔记 匈牙利算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1854字，纯文字阅读大概需要3分钟。

内容图文

众所周知，二分图匹配是二分图理论中的基础，而匈牙利算法是一种求解它的基本算法。事实上，匈牙利算法是一个十分简洁的算法，简介到让人感到惊诧。下面就让我们了解一下这个神奇的算法。

先看几个定义：

• 匹配 匹配是一个边的集合，其中任意两条边都没有公共端点。
• 最大匹配 顾名思义，包含边数最多的匹配
• 交错路 匹配边和非匹配边依次出现的一条路
• 增广路 从非匹配边出发，以非匹配边结束的交错路（增广路长度一定是奇数）

你可能已经被这几个定义搞懵了不过没关系，慢慢看下去你就懂了。

匈牙利算法的基本思想，就是不断地扩大匹配的集合。事实上，他就是一个不断尝试让匹配边数加一的过程。初始状态下，所有的边都是非匹配边，而当算法结束时，我们再也不能让匹配边数变多了，最大匹配数也就求出来了，还能附带求出一种方案。

匈牙利算法基于两个性质：

• 一个匹配\(M\)是最大匹配，当且仅当图中不存在增广路。
• 从某一点出发，如果某个时刻找不到增广路，那么你将永远找不到从该点出发的最短路。

性质1的必要性是显然的（因为增广路长度是奇数），我们先把这两条性质抛开，先来看看这个算法的过程。

我们首先给二分图定向（名字挺高大上，其实就是划分出左部和右部，规定增广路从左部出发）。枚举每一个左部点（想想这个点会不会已经被匹配），如果找不到增广路就算了，如果找到了增广路，我们就把这条路径上所有边的状态取反，于是我们就得到了一种大小+1的匹配。结合代码理解一下 复杂度\(O(nm)\)

int vis[mxn],mch[mxn];//match
inline bool hungary(int x){
    if(vis[x])return 0;vis[x]=1;
//vis记录左部点右部点皆可
    for(int i=first[x];i;i=nxt[i]) //边是单向边
        if(!mch[to[i]] || hungary(mch[to[i]]))return mch[to[i]]=x,1;
    return 0;
}

//main函数
int ans=0;
for(int i=1;i<=n;++i)memset(vis,0,sizeof(vis)),ans+=hungary(i);

如果你没看懂以上代码，那只能是心理原因 我们回过头看这两个性质，性质1显然是算法的基础，而性质2确保了每个点只搜一次。至此我们已经完全理解了匈牙利算法的内在逻辑。

有没有觉得这两个性质很神奇？如果感兴趣可以看看这篇论文，挺好理解的，性质2尤其好理解，有不懂的名词可以百度一下。再次强调，匹配是边集。

好像还有bfs实现的版本，据说常数更小。

以上。

内容总结

以上是互联网集市为您收集整理的学习笔记 匈牙利算法全部内容，希望文章能够帮你解决学习笔记 匈牙利算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---