首先来解释一下什么是欧拉回路
如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。
如果一个回路是欧拉路径，则称为欧拉回路(Euler circuit)。
具有欧拉回路的图称为欧拉图（简称E图）。具有欧拉路径但不具有欧拉回路的图称为半欧拉图。
然后我们再来解释一下度的概念：
无向图中的度值得是边的条数，在有向图中，我们一般不这么说，而是说出度，入度，接下来我们来看一下欧拉回路和欧拉路径与度的关系
无向图存在欧拉回路的条件：
所有的度都是偶数，并且图连通
无向图存在欧拉路径的条件：
除了起点和终点的度可以是奇数外，其余的点的度都是偶数，当然，所有点都是偶数那么是欧拉回路，也自然是欧拉路径
有向图存在欧拉回路的条件：
所有点的出度等于入度，并且图连通
有向图存在欧拉路径的条件：
起点的出度比入度大1，终点的入度比出度大1，其余点的出度等于入度，和上面一样，如果所有的点的出度等于入度，那么是欧拉回路，也自然是欧拉路径
求解欧拉路径有多种算法，其中一种是Hierholzer，个人认为比较简单，而且容易懂，接下来给出算法的实现过程，过程来源于网络（https://www.cnblogs.com/acxblog/p/7390301.html）
Hierholzer算法自动寻找欧拉回路，在找不到欧拉回路的情况下会找到欧拉路径。前提是得给它指定好起点。
算法流程（无向图）：
1.判断奇点数。奇点数若为0则任意指定起点，奇点数若为2则指定起点为奇点。
2.开始递归函数Hierholzer(x):
循环寻找与x相连的边(x,u):
删除(x,u)
删除(u,x)
Hierholzer(u);
将x插入答案队列之中
3.倒序输出答案队列
对于该图，算法的执行流程如下：
1.找到该图没有奇点，从1开始进行Hierholzer算法。
2.删边1-2 递归到2
3.删边2-3 递归到3
4.删边3-7 递归到7
5.删边7-1 递归到1
6.1无边，1加入队列，返回
7.7加入队列，返回
8.删边3-4 递归到4
9.删边4-5 递归到5
10.删边5-6 递归到6
11.删边6-3 递归到3
12.3加入队列，返回
13.6加入队列，返回
14.5加入队列，返回
15.4加入队列，返回
16.3加入队列，返回
17.2加入队列，返回
18.1加入队列，返回
答案队列为：1 7 3 6 5 4 3 2 1。反向输出即为答案。
有向图除判断是否存在有一点点不同以外同理。
至于关于欧拉回路的模板题目可以参考一下该题目
P2731 骑马修栅栏 Riding the Fences https://www.luogu.org/problemnew/show/P2731
完毕
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/59230.html