一、基本概念

欧拉路径:欧拉路是指从图中任意一个点开始到图中任意一个点结束的路径,并且图中每条边通过的且只通过一次

欧拉回路:欧拉回路是指起点和终点相同的欧拉路。


二、存在欧拉路的条件

1.无向连通图存在欧拉路的条件:

所有点度都是偶数,或者恰好有两个点度是奇数,则有欧拉路。若有奇数点度,则奇数点度点一定是欧拉路的起点和终点,否则可取任意一点作为起点。

2.有向连通图存在欧拉路的条件:

  • 每个点的入度等于出度,则存在欧拉回路(任意一点有度的点都可以作为起点)
  • 除两点外,所有入度等于出度。这两点中一点的出度比入度大,另一点的出度比入度小,则存在欧拉路。取出度大者为起点,入度大者为终点。

三、算法实现:

主要分为dfs和并查集两种方法

四、例题

https://www.luogu.org/problemnew/show/P1341

http://acm.hdu.edu.cn/showproblem.php?pid=3018

http://acm.hdu.edu.cn/showproblem.php?pid=1878

五、参考文章

https://www.cnblogs.com/Lewin671/p/8986270.html

https://en.wikipedia.org/wiki/Eulerian/_path#Hierholzer's\_algorithm