欧拉图、欧拉路径、Hierholzer 算法

小鱼儿 2023-10-06 09:59 63阅读 0赞

## 欧拉图、欧拉路径、Hierholzer 算法 ##

本文参考于[【图论】什么是欧拉图？如何求欧拉路径？][Link 1]

#### 不严谨的定义 ####

对于一个连通的图G，有：  
**欧拉路径:** 一条路径，它能够不重复地遍历完所有的边。这个性质很像不重复地一笔画完所有边，所以有些涉及到欧拉路径的问题叫做一笔画问题。  
**欧拉回路：** 一条路径，它能够不重复地遍历完所有的边，并且回到起点。可以看出欧拉回路也是欧拉路径。  
**半欧拉图：** 一个图，图中存在欧拉路径。  
**欧拉图：** 一个图，图中存在欧拉回路。可以看出欧拉图也是半欧拉图。

#### 图与欧拉路径、欧拉回路的结论 ####

**连通的无向图为（半）欧拉图的条件：**  
1.若所有顶点的度为偶数，则能够找到从任意顶点出发的欧拉回路。反之也成立，即若能够找到从任意顶点出发的欧拉回路，则所有顶点的度为偶数。

2.若有且仅有2个顶点的度数为奇数，则只能够找到欧拉路径（路径从这两点中的任一顶点出发，到另一顶点结束）。反之也成立。

**连通的有向图为（半）欧拉图的条件：**  
1.若所有顶点的入度等于出度，则能够找到从任意顶点出发的欧拉回路。反之也成立。

2.若有且仅有两个顶点入度不等于出度，其中一个顶点入度比出度大1，记为V1，另一个顶点入度比出度小1，记为V2，则只能够找到欧拉路径（路径从顶点V2出发，到顶点V1结束）。反之也成立。

**连通的混合图为（半）欧拉图的条件：（混合图是指既有有向边又有无向边的图。）**  
找到一个给每条无向的边定向的策略，使得每个顶点的入度等于出度，这样就能转换成有向图的情况。（这个有待考究）

#### Hierholzer 算法 ####

**问题简述:** 给定一个（半）欧拉图，求欧拉路径。

**Hierholzer 算法思想：**  
当给定的图一定有欧拉路径（回路）时，从一个合理的起始点出发（后面会说什么是合理的），深度优先遍历整个图，遍历过的顶点都不得再遍历，直到遇到的第一个没有可遍历的邻居的顶点，这个顶点一定是某条欧拉路径的终点，把这个顶点“删掉”（实际上不用删，通过标记边已访问就可以不再访问它）后，下一次遇到的没有可遍历的邻居的顶点，一定是这条欧拉路径倒数第二个顶点，再把这个顶点“删掉”再遍历，以此类推，直到把所有没有可遍历的邻居的顶点找到，我们就找到了这条欧拉路径上的所有顶点。

**问题1：**  
可能有人会奇怪，Hierholzer 算法为什么一定能得到欧拉路径？为什么每遇到没有可遍历的邻居的顶点就是欧拉路径上的一个终点？下面以有向图作为说明，无向图同理。这个其实涉及到一个顶点的出度和入度问题。

若从某个顶点开始遍历，遍历过的边不能再遍历，直到无边可遍历为止，当遇到另一个出度等于入度的顶点V  
时，是不可能停留在V的，因为出度等于入度，你进入多少次，一定有对应的出边让你出去多少次。

因此第一个遇到的没有可遍历的邻居的顶点只有两种，一种是它的入度比出度大一，另一种是它的入度与出度相等，但是它是起点（也就是说既是起点又是终点，饶了一圈）。根据前面所说的一些结论（图与欧拉路径、欧拉回路的结论），这两种点都是某条欧拉路径上的终点，所以当我们遇到的没有可遍历的邻居的顶点，尽管放心大胆的把该顶点记录下来，因为它一定是欧拉路径的终点。

**问题2：**  
可能还有人会奇怪，为什么遇到的第二个没有可遍历的邻居的顶点是欧拉路径倒数第二个点？  
我们可以想象一下，我把第一个没有可遍历的邻居的顶点以及对应的边“删掉”后（实际也可以不删，只需标记已经访问过就行），它相邻顶点的出度和入度就会发生变化，在草稿纸画一下你就会发现，它周围的顶点要么变成出度等于入度的顶点，要么变成入度比出度大1的顶点，他们都符合成为欧拉路径的终点的条件，并且由于我们是递归地深度优先遍历，递归返回上一层后，一定是在这些相邻顶点之中，所以这时候遇到的第二个没有可遍历的邻居的顶点，一定是欧拉路径倒数第二个点。

**Hierholzer 算法过程：**  
选择一个合理的点作为起始点，遍历所有相邻边。（一会说什么是合理的点）  
深度优先搜索，访问相邻顶点。将经过的边都不能再访问。  
如果当前顶点没有相邻边，则将顶点入数组末尾。  
最后将数组倒序输出，就是从起点出发的欧拉回路。

**Hierholzer 算法作用：**  
Hierholzer 算法就是证明了，当给定的图一定有欧拉路径（回路）时，按照Hierholzer 算法无脑深度优先搜索，就一定会得到欧拉路径（回路）的逆序。至于得到的是欧拉路径还是欧拉环路，取决于你的图是欧拉图还是半欧拉图，若图为欧拉图，得到的是欧拉环路，若图是半欧拉图，得到的则是欧拉路径。

注意： 若图不是欧拉图也不是半欧拉图，采用Hierholzer 算法得到的结果必定错误。所以在贸然采用Hierholzer 算法前，我们需要先按照前面说的图与欧拉路径、欧拉回路的结论判断图到底是不是（半）欧拉图，若是，才能用该算法去找欧拉路径（回路）。

**什么是合理的起始点：**  
上面说到选择合理的点作为起始点，那么什么点是合理的？这里需要回顾一下前面说的图与欧拉路径、欧拉回路的关系，以无向图为例（有向图同理）：

当图为欧拉图时，能够找到从任意点出发的欧拉回路，此时从任一点出发，都能找到欧拉回路，因此任何一点都是合理的；

当图为半欧拉图时，有且仅有2个顶点的度数为奇数，只能够找到欧拉路径（路径从这两点中的任一点出发，到另一点结束），此时只有从这两点之一出发，才能找到欧拉路径，因此只有这两点是合理的。

[Link 1]: https://blog.csdn.net/a435262767/article/details/105253850