我在做一道题时发现该题目使用了贪心的策略去求最小字典序欧拉路径,但没有人对于这种做法求出来为什么是一个欧拉通路进行证明.我上网查找这个问题时发现两篇博客里分别有一句话对这种东西进行说明:

"(对于有欧拉路径的图)从起点开始，尽可能地不去走桥(走完之后会把图分成两半)，而去走其他边，这样的输出是欧拉路径。"

"(这道题目)然后就是个图上找最小字典序欧拉路径的问题。

两种做法：经典做法，直接递归做，回溯的时候把点丢入栈中，最后倒序输出栈中的点，做之前把边从小到大排序；或者也可以直接贪心选，但是要保证现在走的这条边不是桥。由于这题的特殊性，这个东西是比较好判断的。"

但这些都没有对这种算法为什么求出来是一条欧拉通路(或者说是这样做为什么一定遍历了所有的边)进行证明.

求助关于为什么这种算法是正确的证明.

博客1

博客2