algoHierHolzerEulerPath - 半欧拉图/欧拉图的欧拉路径计算

1 欧拉图基本概念:

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

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

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

欧拉图:具有欧拉回路的图称为欧拉图;

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

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

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

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

  • 2 hierholzer算法

    • 2.1 dfs,当一个节点没邻居了
    • 2.2 将节点入栈reversePath
    • 2.3 dfs完成,reversePath则为逆序栈
  • 3 例子:
    https://media.geeksforgeeks.org/wp-content/uploads/Euler-3.jpg

从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路径