后一情况下找到一条M可扩路，可以对匹配进行一次修改， 过程的反复进行，最终判定G是否有完美匹配或者求出完美 匹配。 根据上面讨论，可设计求偶图的完美匹配算法。 (4)、偶图完美匹配算法 匈牙利算法。 设M是初始匹配。H是扎根于M非饱和点u的交错树。 令：S=VHnx,T=VHnY。 (a)、若M饱和X所有顶点，停止。否则，设u为X中M 非饱和顶点，置S=(u},T=Φ； b)、若NS)=T,则G中不存在完美匹配。否则设y∈NS)-T (c)若y为M饱和点，且yz∈M,置S=SU{z},T=TU{y), 转(b)。否则，设P为M可扩路，置M=M△EP),转(a.0.8 1 0.6 0.4 0.2 0 x t 0 0.5 1 1.5 2 1 0.5 0 0.5 1 n 8 后一情况下找到一条M可扩路，可以对匹配进行一次修改， 过程的反复进行，最终判定G是否有完美匹配或者求出完美 匹配。 根据上面讨论，可设计求偶图的完美匹配算法。 (4) 、偶图完美匹配算法——匈牙利算法。 设M是初始匹配。H是扎根于M非饱和点u的交错树。 令：S=V(H)∩X, T=V(H)∩Y。 (a) 、若M饱和X所有顶点，停止。否则，设u为X中M 非饱和顶点，置S=｛u｝,T=Φ; (b) 、若N(S)=T, 则G中不存在完美匹配。否则设 y ∈N(S) – T. (c ) 若y为M饱和点，且y z ∈M, 置S=S∪｛z｝, T=T∪｛y｝, 转(b)。否则，设P为M可扩路，置M1=MΔE(P)，转(a)