欧拉路径和欧拉回路(Euler Path and Euler Circuit)解释-Toy模板网

这篇具有很好参考价值的文章主要介绍了欧拉路径和欧拉回路(Euler Path and Euler Circuit)解释。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

欧拉路径(欧拉回路）是图论非常重要的组成部分，欧拉路径是数学家欧拉在研究著名的德国哥尼斯堡(Koenigsberg)七桥问题时发现的。这一发现直接导致了一门新的理论研究的诞生-图论问题。
欧拉路径和欧拉回路区别
在一个连通图上，如果从一个顶点出发，历经访问所有的边，访问边的次数规定有且仅有一次，回到另外一个顶点，那么这个连通图中就包含欧拉路径。
为了更好的理解，我们从以绿色顶点为起点，对无向图中的8条边，访问1次且仅为1次后，最后到达桔色终点。按照1-2-3-4-5-6-7-8的次序访问，此路径便形成一条欧拉路径。另外，下述无向图的欧拉路径的访问次序不唯一，读者可以考虑以下其它访问次序的可能性。

欧拉通路,算法,深度优先,图论
值得一提的是，上图中的欧拉路径虽然有不同的顺序，当时起点/终点（可以互换）必须保持不变，如果选择从除这两点之外的其它点出发，是无法完成欧拉路径的遍历过程的。
上面讨论的都是欧拉路径，读者就会问，那什么是欧拉回路(Euler Circuit)呢? 欧拉回路实际上是一类特殊的欧拉路径，其本身属于欧拉路径，同时需要起点和终点在同一点，满足起点和终点为同一点的欧拉路径就是欧拉回路。为了让大家更清晰理解，我们以图为例。
欧拉通路,算法,深度优先,图论
在欧拉路径的基础上，我们通过#9号边和#10号边，让之前滞留在对面的终点重新回到起点。欧拉回路可以从图中的任意一点开始，都可以回到此点，所以欧拉回路可以有多种遍历形式。
3. 欧拉路径和欧拉回路的算法思想，欧拉路径算法思想包含Hierholzer算法和Fleury算法。在常规的DFS顶点遍历过程中，图中，只要完成所有的顶点的遍历即可，处理的对象为顶点，那么对于欧拉路径而言就会造成一个问题，backedge或者forwardedge由于共享的顶点已经标记为访问，那么这些边就会自动跳过，从而无法完成所有边的访问。
Hierholzer的通过转换操作对象，对边的访问进行标记，按照边是否访问，来控制DFS的操作。
Fleury算法核心思想是，每次访问边的邻接顶点之前，需要确认此边不是bridge，如果不是bridge类型的边，就继续访问，如果是那么就寻找其它合理的边再进行访问。
4. 接下来要讨论的问题是，什么样的连通图具有欧拉路径或欧拉回路呢？我们需要分有向图和无向图两类情况进行讨论。

对于有向连通图，如果图中所有的顶点的出度和入度相等，那么此有向连通图就为欧拉回路；如果此有向连通图中，有一个顶点的出度比入度多1，另外一个顶点的入度比出度多1，且除了这两个顶点之外的其它顶点，其出度和入度相等。除此之外，此有向连通图中不包含欧拉路径或欧拉回路。
对于无向连通图，如果所有顶点的度均为偶数，那么此无向连通图中包含欧拉回路，如果仅有两个顶点的度为奇书，那么此无向连通图中包含欧拉路径。除此之外，其它情况下，此无向连通图中不好含欧拉路径或欧拉回路。

欧拉通路,算法,深度优先,图论
5. 总结
通过对欧拉路径和欧拉回路的梳理，进一步了解二者的区别，同时也可以通过对顶点的度的判断，确认连通图中是否包含欧拉路径或欧拉回路。后续的博文中，我们将对两类经典算法进行分析和Coding.
谢谢
以上