-
二分匹配及其应用——匈牙利算法的基本步骤（HDUACM2010版_13）
资源介绍
匈牙利算法——基本步骤：
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；