本文转自大客:http://www.byvoid.com/blog/hungary/
这是一种用增广路求二分图最大匹配的算法。它由匈牙利数学家Edmonds于1965年提出,因而得名。 定义 未盖点:设Vi是图G的一个顶点,如果Vi 不与任意一条属于匹配M的边相关联,就称Vi 是一个未盖点。
交错路:设P是图G的一条路,如果P的任意两条相邻的边一定是一条属于M而另一条不属于M,就称P是一条交错路。
可增广路:两个端点都是未盖点的交错路叫做可增广路。
流程图
伪代码:
演示:
C实现(作者BYVoid)
Pascal实现(作者魂牛)
ps:最近因为比赛,需要用到二分图,图论这东西好多要好好学的。
分享到:
相关推荐
匈牙利算法指派问题matlab代码
给出了指派问题的匈牙利算法的编程实现,通过调试。
匈牙利算法在企业员工指派问题的应用
matlab实现匈牙利算法二分图最大匹配的程序
程序实现了匈牙利算法应用于指派问题,输入指派成本矩阵C,给出最小成本及使得成本最小的最优指派
有关二分图匹最大配问题,利用匈牙利算法可以高效的解决
用于运筹学项目的matlab中的匈牙利算法实现 问题陈述 电子商务:计算折扣的算法 场景是: • 电子商务网站 • 大量产品 • 这些产品上混合有大量折扣 产品由唯一的 ProductID 标识并具有销售价格。很经典的场景。...
用java实现的匈牙利算法,
C++ 匈牙利算法 模板,非常简洁易理解
匈牙利算法-邻接表实现 还有一些注释,应该很清楚
匈牙利算法的基本思想是修改效益矩阵的行或列,使得每一行或列中至少有一个为零的元素,经过修正后,直至在不同行、不同列中至少有一个零元素,从而得到与这些零元素相对应的一个完全分配方案。 当它用于效益矩阵时...
分配问题 是管理数学中线性规划的一个重要类型。 它可以用单纯形法求解 , 但 由于其模型的特殊性 , 一般都采用特殊的解法--匈牙利算法。匈本文利用矩阵给出了匈牙利算法的理论依据。
匈牙利算法及程序,很好的描述了匈牙利算法的具体定义,并将程序展示出来
matlab匈牙利算法求解指派问题
用C语言写的匈牙利算法,并报含有运行文件,可以自动执行运算
实现计算二分图最大匹配的匈牙利算法,用的是C++\C语言
匈牙利算法的MATLAB 程序代码,可以学习匈牙利算法的MATLAB的程序
用matlab语言遗传算法实现的匈牙利算法
关于匈牙利算法的MATLAB代码例子,值得借鉴学习
C++实现的匈牙利算法。进行了相关测试,测试成功; 匈牙利算法分配优化算法