【文件属性】：
文件名称：匈牙利算法——基本步骤-（HDUACM2010版_13）二分匹配及其应用
文件大小：339KB
文件格式：PPT
更新时间：2021-04-23 17:20:09
杭电ACM课件 ACM
匈牙利算法——基本步骤：
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；