| 查看: 287 | 回复: 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 ] |
回复此楼» 猜你喜欢
大家散了吧，后缀研究没有意义，别浪费时间了，过好目前的每一天，不要焦虑
已经有6人回复
-
固定端突然变了，今天
已经有6人回复
-
听说今天filecode变了
已经有25人回复
-
基金中了
已经有4人回复
-
filecode
已经有10人回复
-
filecode
已经有12人回复
-
一个有机合成实验室都需要哪些设备？
已经有12人回复
-
求各位大神看下
已经有33人回复
-
咨询面上基金
已经有7人回复
-
影响面上的因素
已经有11人回复
找到一些相关的精华帖子，希望有用哦~
求助，有关于立体匹配中的tsukuba图像
已经有9人回复
- 求助一种组合算法
已经有6人回复
- 【求助】计算机辅助药物设计
已经有9人回复
- 【求助】结果文件中字符串的搜索程序
已经有5人回复
- 【求助】相似度的算法
已经有7人回复
- 【求助】求教K-D树的BBF搜索算法
已经有7人回复
点击这里搜索更多相关资源科研从小木虫开始，人人为我，我为人人
50