algoHierHolzerEulerPath - 半欧拉图/欧拉图的欧拉路径计算
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