一、基本概念
欧拉路径:欧拉路是指从图中任意一个点开始到图中任意一个点结束的路径,并且图中每条边通过的且只通过一次。
欧拉回路:欧拉回路是指起点和终点相同的欧拉路。
二、存在欧拉路的条件
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