关于欧拉图的路径问题

· · 个人记录

众所周知，欧拉图的路径要逆序输出。

这是为什么呢？

看下面这个图。

会发现这是一个半欧拉图（就是只有欧拉路径没有回路）。

正确的且字典序最小的路径是：1 2 4 5 2 3。

但是如果是直接输出的话，会输出1 2 3 4 5 2。显然是错误的。

其实逆序的作用就是把欧拉路中的终点放在最后输出（起点一定是最后一个加入栈的，而终点因为度数为1所以一定是第一个入栈的）。在欧拉回路中，逆序压栈与顺序都可以。

不过只要记得逆序压栈就好了吧，正不正确管它呢。