首页 > 代码库 > 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 (弗罗莱) 算法通俗解释