| 查看: 240 | 回复: 0 | ||
hdu016至尊木虫 (著名写手)
|
[求助]
求助匹配算法的实现
|
|
出处：算法设计技巧与分析(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 ] |
回复此楼» 猜你喜欢
265求调剂
已经有9人回复
-
085600材料与化工调剂
已经有20人回复
-
专硕 351 086100 也是考的材科基 本科也是材料
已经有6人回复
-
085600专硕材料与化工348分求调剂
已经有10人回复
-
085600 295分求调剂
已经有21人回复
-
285求调剂
已经有5人回复
-
一志愿安徽大学0817化学工程与技术，求调剂
已经有9人回复
-
一志愿0817化学工程与技术，求调剂
已经有8人回复
-
271分求调剂学校
已经有3人回复
-
生物学308分求调剂（一志愿华东师大）
已经有7人回复
找到一些相关的精华帖子，希望有用哦~
求助，有关于立体匹配中的tsukuba图像
已经有9人回复
- 求助一种组合算法
已经有6人回复
- 【求助】计算机辅助药物设计
已经有9人回复
- 【求助】结果文件中字符串的搜索程序
已经有5人回复
- 【求助】相似度的算法
已经有7人回复
- 【求助】求教K-D树的BBF搜索算法
已经有7人回复
点击这里搜索更多相关资源科研从小木虫开始，人人为我，我为人人
