边连通
回路$∈$路径

无向图的欧拉路径

我们可以发现, 一个图对于起点和终点来说, 如果两个点不同, 我们走到了终点, 如果不是最后一条边的话, 我们就需要走出去, 最后一条边就不用出去了, 所以我们可以看出终点的度数一定为奇数, 起点同理, 如果起点终点相同的话, 即回路, 即度数为偶数., 对于其他点来说走过了, 就要走出来, 所以入度为偶数.

有向图的欧拉路径

同上思考方式.

结论

算法细节

• 算法原理
  
• 时间复杂度
  
  例题及优化模板 数据范围较大时使用

例题 朴素模板求欧拉路径的最小字典序方案

例题 判断有向图是否存在欧拉路径