24小时热门版块排行榜

返回列表

hdu016

至尊木虫 (著名写手)

应助: 20 (小学生)
金币: 13318.1
散金: 11
红花: 1
帖子: 1556
在线: 263.4小时
虫号: 1352383
注册: 2011-07-21
性别: GG
专业: 系统科学与系统工程

[求助] 求助匹配算法的实现

出处：算法设计技巧与分析(Algorithms Design Techniques and Analysis)，作者<沙特>M.H.Alsuwaiyel著，译者：吴伟昶，方世昌，电子工业出版社。
这本书中的第十七章<匹配>中的任意图的匹配算法(276页开始，算法17.3)。

具体算法如下：

算法17.3 GMATCH
输入：无向图G=(V,E)。
输出：G中的最大匹配。

1. M  ←{ }  { 初始化M为空匹配 }
2. maximum ←  false
3. while not maximum
4. 决定与M有关的自由顶点集F
5. augment ←  false
6. while  F≠ { } and not augment
7.    清空栈、未标记边，从顶点删除标记
8.    设 x 为下一个顶点；F ←  F - {x}；T  ←  x
9.    标记x为外部的  { 初始化交替路径树 }
10.    hungarian ←  false
11.    while not augment
12.          选择一个外部顶点x和一条未标记的边 (x,y)
13.          if (x, y) 存在 then  标记  (x,y)
14.          else
15.             hungarian ←  true
16.             exit  this  while loop
17.          end if
18.          if y为内部的 then do nothing  { 找到偶数长的回路 }
19.          else if y为外部的  then  { 找到花 }
20.             将花放在栈顶，收缩它
21.             用顶点w替换花，标记w为外部的
22.             如果花包含根，则标记w为自由的
23.          else if y为自由的 then
24.                augment  ←  true
25.                F ←  F - { y}
26.          else if
27.          else
28.             设(y,z)在M中，将(x,y)和(y,z)加入T中
29.             标记y为内部的，z为外部的
30.          end if
31.    end while
32.    if hungarian then 将T从G中删除
33.    else if augment then
34.       用下列方法构造p
35.       从栈中弹出花，展开它们，增加偶数长部分
36.       用p增广G
37.       end if
38.    end while
39.    if not augment then maximum ←  true
40. end while

希望得到帮助啊!!!

[ Last edited by hdu016 on 2012-5-17 at 15:50 ]

回复此楼