【读书笔记】算法漫步 第4章

问题2 一笔画问题

哥尼斯堡七桥问题

图论

欧拉

这几个词，不知道，非计算机专业的人知道几个。

如果不知道，建议在智能手机上安装“一笔画”这个游戏APP，玩一玩，算一个智力休闲游戏吧。然后百度一下哥尼斯堡七桥问题，了解一下图论的起源，了解图论之父欧拉。

 

要描述一笔画问题，必须使用图论中的术语。

一笔画问题：能否从一个节点开始，沿着一条边到它的某一个相邻节点，如此继续，最后返回出发节点，中间每条边恰好经过1次。

 

欧拉提出的欧拉定理，可以判断一个图是否可以实现“一笔画”。

 

求一个欧拉图的欧拉路径，也就是求一笔画。有两个有名的算法：

 

一个是Fleury算法，这个算法的算法思想，是不断删除边，但要保证留下的图总保持是欧拉图（去掉孤立节点），且当前节点是算法的合法起始节点。书中详细描述了Fleury算法，还用归纳法给出了算法正确性证明描述。这个算法的思想比较容易理解，简单说，就是如果把走过的边，因为不能再走了，看作删除，那每走一步，不能让剩余的图变为不连通图，否则就无法走完所有边。这个利用图论中，桥的概念，就容易设计出算法。但是这个算法的性能不佳。

另一个是Hierholzer算法，简单说，这个算法是利用图的深度优先算法，不断找环路，然后删除环路，最终可以求得欧拉路径。估计是设计太多图论、数据结构和算法知识，本书没有说明。

另外，本章也提到了著名的“中国邮递员问题”，有兴趣的读者，可以自己百度Hierholzer算法和中国邮递员问题，进行扩展阅读。

 

 

【作者感受】

图和图的算法，是计算机核心课程中重点核心内容之一。

图，即看的见，又看不见，数学中有图论，计算机实现图的求解算法都很烧脑，能够学习和感受图算法的美，真好。