设为首页 - 加入收藏
广告 1000x90
您的当前位置:2019年全年最准资料 > 布达佩斯 > 正文

匈牙利算法--过程图解

来源:未知 编辑:admin 时间:2019-07-11

  以下算法可把G中任一匹配M扩充为最大匹配,此算法是Edmonds于1965年提出的,被称为

  (1)首先用(*)标记X中所有的非M-顶点,然后交替进行步骤(2),(3)。

  (2)选取一个刚标记(用(*)或在步骤(3)中用(yi)标记)过的X中顶点,例如顶点xi,然后用(xi)去标记Y中顶点y,如果xi与y为同一非匹配边的两端点,且在本步骤中y尚未被标记过。重复步骤(2),直至对刚标记过的X中顶点全部完成一遍上述过程。

  (3)选取一个刚标记(在步骤(2)中用(xi)标记)过的Y中结点,例如yi,用(yi)去标记X中结点x,如果yi与x为同一匹配边的两端点,且在本步骤中x尚未被标记过。重复步骤(3),直至对刚标记过的Y中结点全部完成一遍上述过程。

  (Ⅰ)标记到一个Y中顶点y,它不是M-顶点。这时从y出发循标记回溯,直到(*)标记的X中顶点x,我们求得一条交替链。设其长度为2k+1,显然其中k条是匹配边,k+1条是非匹配边。

  (4)当(2),(3)步骤中断于情况(Ⅰ),则将交替链中非匹配边改为匹配边,原匹配边改为非匹配边(从而得到一个比原匹配多一条边的新匹配),回到步骤(1),同时消除一切现有标记。

  (5)对一切可能,(2)和(3)步骤均中断于情况(Ⅱ),或步骤(1)无可标记结点,算法终止(算法找不到交替链)。

  我们不打算证明算法的正确性,只用一个例子跟踪一下算法的执行,来直观地说明这一点。

  (2)找到交替链(x1,y1)(由标记(x1),(*)回溯得),置M={(x1,y1)}。

  (4)找到交替链(x3,y1,x1,y4)(如图9.4所示。图中虚线表示非匹配边,细实线表示交替链中非匹配边,粗实线表示匹配边),因而得M={(x2,y2),(x3,y1),(x1,y4)}。

  (6)找到交替链(x5,y4,x1,y1,x3,y7)(如图9.5所示,图中各种线段的意义同上),因而得

本文链接:http://dicaspace.com/budapeisi/2730.html

相关推荐:

网友评论:

栏目分类

现金彩票 联系QQ:24498872301 邮箱:24498872301@qq.com

Copyright © 2002-2011 DEDECMS. 现金彩票 版权所有 Power by DedeCms

Top