《匈牙利算法》由会员分享，可在线阅读，更多相关《匈牙利算法（3页珍藏版）》请在金锄头文库上搜索。
1、匈牙利算法过程图解以下算法可把G中任一匹配M扩充为最大匹配，此算法是Edmonds于1965年提出的，被 称为匈牙利算法，其步骤如下：（1）首先用（*）标记X中所有的非M-顶点，然后交替进行步骤（2）,（3）。（2）选取一个刚标记（用（*）或在步骤（3）中用（片）标记）过的X中顶点，例如顶 点片，然后用（xi）去标记Y中顶点y,如果xi与y为同一非匹配边的两端点，且在本步骤 中y尚未被标记过。重复步骤（2），直至对刚标记过的X中顶点全部完成一遍上述过程。（3）选取一个刚标记（在步骤（2）中用（xi）标记）过的Y中结点，例如右，用（右） 去标记X中结点x,如果yi与x为同一匹配边的两端点，且在本
2、步骤中x尚未被标记过。 重复步骤（3），直至对刚标记过的Y中结点全部完成一遍上述过程。（2），（3）交替执行，直到下述情况之一出现为止：（I）标记到一个Y中顶点y,它不是M-顶点。这时从y出发循标记回溯，直到（*）标 记的X中顶点x,我们求得一条交替链。设其长度为2k+1,显然其中k条是匹配边，k+1 条是非匹配边。（II）步骤（2）或（3）找不到可标记结点，而又不是情况（I）。（4）当（2）,（3 ）步骤中断于情况（I）,则将交替链中非匹配边改为匹配边，原 匹配边改为非匹配边（从而得到一个比原匹配多一条边的新匹配），回到步骤（1）,同时 消除一切现有标记。（5）对一切可能，（2）和（3）步骤
3、均中断于情况（II）,或步骤（1）无可标记结点， 算法终止（算法找不到交替链）。我们不打算证明算法的正确性,只用一个例子跟踪一下算法的执行，来直观地说明这一点。 例9.3用匈牙利算法求图9.3的一个最大匹配。（1）置M =比，对x-x标记（*）。1 6（2） 找到交替链（X, y1）（由标记（x1）,（*）回溯得），置M = （X, y1）0（3） 找到交替链（x2, y2）（由标记（x2）,（*）回溯得），置 M = （X, y1）, （x2, y2）,。（4）找到交替链（x3, y1? X, y4）（如图9.4所示。图中虚线表示非匹配边，细实线表示 交替链中非匹配边，粗实线表示匹配边），因而得M = （x2, y2）, （x3, y1）,（x1, y4）。（5） 找到交替链（x4, y3）（由标记（x4） , （*）回溯得）,置 M = （x2, y2）, （x3, y1）,（x1, y4）, （x43）。（6） 找到交替链（x5, y4, X, y1? x3, y7）（如图9.5所示，图中各种线段的意义同上），因 而得图艮弘Y1旳Y40ye
