首页 > 代码库 > Fleury (弗罗莱) 算法通俗解释
Fleury (弗罗莱) 算法通俗解释
Fleury (弗罗莱) 算法通俗解释
1.定义
2.举例说明
图2为连通图G,现利用Fleury算法求它的欧拉通路。(注意区分:欧拉通路、欧拉回路)
其中一种欧拉通路如下:4 5 8 7 6 8 9 1 5 3 2 4 6,其搜索路径如下图所示:
现在让我们来分析算法实现过程:
假设我们这样走:4,6,8,5,此时在5处有三种选择(3,4,1),那么哪种能走通哪种走不通呢?答案是(3,4)通,1不通。为什么呢?来看下图…
分析:
因为(5~1)之间的边是除去已走过边(E(G)-{E1(4~6),E2(6~8),E3(8~5)})图G的一个桥,所谓桥即去掉该边后,剩下的所有顶点将不能够连通,即无法构成连通图。
而选择(5~3)和(5~4)则满足定义中第二条(b)中的要求。当然当(5~3)和(5~4)都不存在,即定义中所说“除非无别的边可供选择时”,此时就就可以选择(5~1),其他情况下一定要优先选择非桥的边,否则就可能出现无法走通的情况。也就是说该搜索方法无法构成欧拉通路。如下图是选择(5~1)的后果:
而(5~3)和(5~4)则可以顺利完成欧拉图通路的搜索,具体算法实现网上很多,不是本文讨论重点。相信有了算法思想,算法的实现应该不难,有时间我会完善代码。
另外:譬如洒水车问题也是利用欧拉通路解决的经典问题。
Fleury (弗罗莱) 算法通俗解释
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。