博客

1 欧拉图基本概念：

圈：任选图中一个顶点为起点，沿着不重复的边，经过不重复的顶点为途径，之后又回到起点的闭合途径称为圈。

欧拉路径：通过图中所有边一次且仅一次遍历所有顶点的路径称为欧拉(Euler)路径；

欧拉回路：通过图中所有边一次且仅一次行遍所有顶点的回路称为欧拉回路；

欧拉图：具有欧拉回路的图称为欧拉图；

半欧拉图：有欧拉路径但没有欧拉回路的图称为半欧拉图。

欧拉图与半欧拉图的判定：

G是欧拉图 ⇔ G中所有顶点的度均为偶数 ⇔ G是若干个边不重的圈的并。

G是半欧拉图 ⇔ G中恰有两个奇数度顶点。

• 2 hierholzer算法

  • 2.1 dfs，当一个节点没邻居了
  • 2.2 将节点入栈reversePath
  • 2.3 dfs完成，reversePath则为逆序栈

• 3 例子：
  
  

从0开始的话，那么

访问栈为：0 -> 1 -> 2 -> 0, 此时reversePath可以将访问栈里的0弹出加入，则reversePath = [0, 2]

此时访问栈为： 0-> 1 ，接着访问3，4,然后弹出4，3，1，0

则 reversPath = [0,2,4,3,1,0]，然后逆序则为：

0 1 3 4 2 0，为目标的eular path

2 一句话总结hierhozer算法: dfs后续遍历节点的逆序为eular路径