博客

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）则可以顺利完成欧拉图通路的搜索，具体算法实现网上很多，不是本文讨论重点。相信有了算法思想，算法的实现应该不难，有时间我会完善代码。

另外：譬如洒水车问题也是利用欧拉通路解决的经典问题。

参考文章：http://www.cnblogs.com/Lyush/archive/2013/04/22/3036659.html