环球科创网

匈牙利算法详细步骤(匈牙利算法)

更新时间:2023-11-04 11:03:15

导读 大家好,我是小环,我来为大家解答以上问题。匈牙利算法详细步骤,匈牙利算法很多人还不知道,现在让我们一起来看看吧!1、谈匈牙利算法自...

大家好,我是小环,我来为大家解答以上问题。匈牙利算法详细步骤,匈牙利算法很多人还不知道,现在让我们一起来看看吧!

1、谈匈牙利算法自然避不开Hall定理,即是:对于二部图G,存在一个匹配M,使得X的所有顶点关于M饱和的充要条件是:对于X的任意一个子集A,和A邻接的点集为T(A),恒有: │T(A)│ >= │A│ 匈牙利算法是基于Hall定理中充分性证明的思想,其基本步骤为: 1.任给初始匹配M; 2.若X已饱和则结束,否则进行第3步; 3.在X中找到一个非饱和顶点x0,作V1 ← {x0}, V2 ← Φ; 4.若T(V1) = V2则因为无法匹配而停止,否则任选一点y ∈T(V1)V2; 5.若y已饱和则转6,否则做一条从x0 →y的可增广道路P,M←M?E(P),转2; 6.由于y已饱和,所以M中有一条边(y,z),作 V1 ← V1 ∪{z}, V2 ← V2 ∪ {y}, 转4; 设数组up[1..n] --- 标记二分图的上半部分的点。

2、 down[1..n] --- 标记二分图的下半部分的点。

3、 map[1..n,1..n] --- 表示二分图的上,下部分的点的关系。

4、 True-相连, false---不相连。

5、 over1[1..n],over2[1..n] 标记上下部分的已盖点。

6、 use[1..n,1..n] - 表示该条边是否被覆盖 。

7、 首先对读入数据进行处理 ,对于一条边(x,y) ,起点进集合up,终点进集合down。

8、 标记map中对应元素为true。

9、 1. 寻找up中一个未盖点 。

10、 2. 从该未盖点出发 ,搜索一条可行的路线 ,即由细边出发, 由细边结束, 且细粗交错的路线 。

11、 3. 若找到 ,则修改该路线上的点所对应的over1,over2,use的元素。

12、重复步骤1。

13、 4. 统计use中已覆盖的边的条数total,总数n减去total即为问题的解。

本文到此讲解完毕了,希望对大家有帮助。

免责声明:本文由用户上传,如有侵权请联系删除!