一、基本概念

歐拉路徑：歐拉路是指從圖中任意一個(gè)點(diǎn)開始到圖中任意一個(gè)點(diǎn)結(jié)束的路徑，并且圖中每條邊通過的且只通過一次。

歐拉回路：歐拉回路是指起點(diǎn)和終點(diǎn)相同的歐拉路。

---

二、存在歐拉路的條件

1.無(wú)向連通圖存在歐拉路的條件：

所有點(diǎn)度都是偶數(shù)，或者恰好有兩個(gè)點(diǎn)度是奇數(shù)，則有歐拉路。若有奇數(shù)點(diǎn)度，則奇數(shù)點(diǎn)度點(diǎn)一定是歐拉路的起點(diǎn)和終點(diǎn)，否則可取任意一點(diǎn)作為起點(diǎn)。

2.有向連通圖存在歐拉路的條件：

• 每個(gè)點(diǎn)的入度等于出度，則存在歐拉回路（任意一點(diǎn)有度的點(diǎn)都可以作為起點(diǎn)）
• 除兩點(diǎn)外，所有入度等于出度。這兩點(diǎn)中一點(diǎn)的出度比入度大，另一點(diǎn)的出度比入度小，則存在歐拉路。取出度大者為起點(diǎn)，入度大者為終點(diǎn)。

---

三、算法實(shí)現(xiàn)：

主要分為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?

總結(jié)

以上是生活随笔為你收集整理的欧拉路径(Euler_Path)和欧拉回路(Euler_Loop)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。