欧拉图和一笔画游戏
原创约 2260 字
一句话总结
「一笔画」游戏的本质是寻找欧拉路径/欧拉回路，可以通过节点的度数判断是否存在欧拉路径/欧拉回路。
Hierholzer 算法是用于计算欧拉路径/欧拉回路的经典算法，它是 图结构 DFS 算法 的拓展。
欧拉图是图论中的经典概念，起源于著名的哥尼斯堡七桥问题。这个问题不仅在数学史上具有重要意义，在现代计算机科学中也有广泛应用，比如路径规划、电路设计等。
考虑到这是基础章节，所以不会详细讲解代码实现，具体的算法代码以及习题会安排在数据结构章节的图论部分讲解。
本文主要介绍欧拉图的定义、经典的七桥问题、欧拉路径和欧拉回路的概念，以及寻找欧拉路径的技巧，你可以在本站配套的一笔画小游戏中直观地感受到。
一笔画游戏
我记得小时候玩过「一笔画」小游戏，规则就是要求你一笔连接所有的点和边，其中点可以重复经过，但每条边必须恰好经过一次，不能重复经过。
网站配套的游戏面板也收录了这个小游戏：
小时候玩这种游戏就是全靠运气，随便选择起点开始乱走一通，能走完就走完，走不完就重新开始。
后来才知道这个益智小游戏其实是一个经典的图论算法，而且有套路可循。
现在就可以告诉你完成游戏的套路：
- 如果所有节点的度数都是偶数，那么可以从任何节点开始，一定可以完成一笔画，且最终会回到起点。
- 如果只有两个节点的度数为奇数，那么必须从这两个奇数度节点中的任意一个开始，才能完成一笔画。
- 如果上面两种情况都不满足，那么无法完成一笔画。
游戏面板中会显示每个节点的 度数，你可以先试试看这个套路好不好用：）
下面我们来介绍这个小游戏背后的图论知识 - 欧拉图。
七桥问题
欧拉图的概念源于 18 世纪著名的哥尼斯堡七桥问题。当时的哥尼斯堡（现在的加里宁格勒）有一条河流将城市分为南北两岸，河中有东西两个小岛，有七座桥连接着北岸、南岸、东岛和西岛。
问题是：能否设计一条路线，从任意一个区域出发，经过每座桥恰好一次，最后回到起点？
我们可以将这个问题抽象成图论问题：
在这幅图中：
- 每个区域对应一个节点
- 每座桥对应一条边
- 问题转化为：是否存在一条路径，经过图中每条边恰好一次，且最终回到起点
最终，欧拉通过数学证明七桥问题无解，从而解决了这个著名问题。
术语定义
基于七桥问题，我们引入几个图论术语：