用dfs求欧拉路的正确性

· · 个人记录

分两种情况讨论。

1.当图中仅有两个奇点时,图上存在欧拉路,起点与终点分别是两奇点。 dfs算法从其中一个起点开始,删掉起点连出的一条边,此时起点变为偶点,再考虑起点连出的点:

如果是终点,那么终点变为偶点,此时图中仅存在偶点,证明删掉此条边还存在欧拉回路;

如果是普通点,那么普通点由偶变奇点,可以把此点看做新的起点,图中仍然存在欧拉路。

然后对邻居节点继续遍历,相当于删去一条边,缩小了图,但可以证明删去后仍存在欧拉路或欧拉回路,并且因为dfs序遍历,遍历的路径是连续的,可证明算法正确性。

2.图中没有奇点时同理。

可能存在漏洞,欢迎完善。