算法的乐趣实战（1）--匈牙利算法

内容导读

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

内容图文

在阅读《算法的乐趣》的时候，实在难以理解第七章中关于匈牙利算法的描述，所以劣者在网上搜刮各种资料，整理如下，既为了自己复习之用，也为了后来者的方便

 

匈牙利算法解决了舞伴的快速匹配问题，什么是舞伴快速匹配问题呢？男女双方都有各自的最优选择名单，在一轮轮的选择过后，最终会得到一个结果，这个过程就是快速匹配问题。

匈牙利算法如下：

定义

struct tagMaxMatch
{
int edge[MAX][MAX];    //顶点和关系的图
bool on_path[MAX];       //当前节点是否在增广路径上
int path[MAX];        //当前找到的增广路径（原来的yj在和谁配对？）
int max_match;    //如果最后！=MAX,就是查找失败
}

算法如下

bool findPath(GRAPH_MATCH *match, int xi)//对于这个xi节点来说
{
    for(int jy=0;jy<MAX;jy++)
        {
        if((match->edge[xi][yj]==1) && (!match->on_path[yj])//如果真实存在这条路 && 这个点不在我的增广路上
            match->on_path[yj]=true;
            if( (match->path[yj]==-1) || findPath(match,match->path[yj]) )
            //这个点正好是“新”点，或者让这个点的原主人滚蛋，让他去寻找“新“点
            {        //如果成功了
                match->path[yj]==xi;       //插上我的小旗，女伴是我的了
                return true;
            }
        }
 }
                

当然这个只是一个点作为起点的算法，完整算法需要遍历所有的xi，同时注意每次遍历前要将on_path归零（为了让其他人来把他踹开>_<)

算法的复杂度：遍历所有的边O（E），所有的节点O（V），结果就是O(V*E)，还挺高效

这个算法讲究的就是一个”将就“，有人来，那么这个人就是上上宾，其他人都要依次让一让（按照算法，退让也有优先级），大概也是一种中庸的社会态度吧。

内容总结

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

内容备注

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

内容手机端

---