首页 / 算法 / Edmonds 开花算法
Edmonds 开花算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Edmonds 开花算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含551字，纯文字阅读大概需要1分钟。
内容图文
Edmonds 开花算法
input：
图G，匹配M，未饱和点u
idea：
查找从 u 开始的 M-交错路径， 对每个顶点记录父亲节点。 发现花朵，则收缩。
维 护 S 和 T，S 表示沿着已经饱和的边抵达的顶点构成的集合，收缩过程中的新顶点也属于 S，
T表示当前图中沿着未饱和的边抵达的顶点构成的集合 ，一旦遇到另一个未饱和的顶点，则得到增广路。
init：
S = { u }， T = ?
iterate：
若 S 中无未饱和的点，则不存在从 u 开始的增广路，算法停止。
否则，取出一个未饱和的顶点 v ∈ S，依次考虑 y ? T 的任意顶点 y ∈ N( v )。
若 y 未被 M 饱和，则从 y 开始回溯，若有必要，则开花，输出增广路。
若 y ∈ S，则找到花朵，收缩花朵，用产生的新的顶点替代 S 和 T 中的对应的顶点，
从产生的新图这种新点开始搜索。
否则，y 被 M 匹配到某个顶点 w，将 y 记录由 v 可达并放入 T 中，将 w 标记为由 y 到达并放入 S 中。
处理完 v 所有相邻点后，标记 v，继续迭代。
原文：http://blog.csdn.net/pandora_madara/article/details/42051145
内容总结
以上是互联网集市为您收集整理的Edmonds 开花算法全部内容，希望文章能够帮你解决Edmonds 开花算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。