# Euler路徑與Euler圖
> 上一篇文章 [拓樸排序](https://hackmd.io/BeMu5-jOSre5GEGsbk3CmQ)
> 下一篇文章 [堆積排序](https://hackmd.io/HbcFW4cMTySYBFtzzowE9Q)
> 先備知識 無
> 延伸閱讀 無
---
# 概述
大家應該都聽過所謂的「一筆畫問題」，轉換成圖論版本就是：找到一條行跡（不重複
經過邊的路徑）使其經過一張圖上所有的邊。這就是所謂的「歐拉路徑」（Eulerianpath），
而如果要求起終點相同，就稱為「歐拉迴路」（Euleriancircuit）。
>下圖為範例圖
>
# 如何判斷圖是否可以形成Euler路徑與Euler圖
| | Euler Circuit | Euler Path |
| -------- | -------- | -------- |
| 無向圖 | 圖中每個節點的邊的個數為偶數，且圖形需要聯通 | 所有點中，只有兩個點的邊的個數是奇數，且圖形需要聯通，或者符合無向圖的Euler Circuit|
| 有向圖 | 圖中每個節點進入邊的個數要等於出去邊的個數，且圖形需要聯通 | 所有點中只有一個點出去的邊個數多於進入的邊個數一個，且此點為起點。同時只有另一個點進入的邊個數多於出去的邊個數一個，此為終點。且圖形需要聯通，或者符合有向圖的Euler Circuit |
# 程式實作
## Eulerian Path(無向圖)
>以下圖為例
>
### 步驟一： 初始化圖的結構
```python=4
from collections import defaultdict
class EulerianPath:
def __init__(self):
self.graph = defaultdict(list) # 無向圖：每個節點對應一個鄰居 list
self.path = [] # 最後的 Eulerian 路徑（反向記錄）
```
:::spoiler 什麼是`defaultdict(list)`（點我展開）
Python 的 defaultdict 是 collections 模組提供的一種 字典（dict）加強版，它的特色是：
如果你訪問一個不存在的 key，它不會報錯，而是自動建立一個「預設值」
:::
>`graph` 是鄰接表，使用 `defaultdict(list)` 來自動建立 list。
>`path` 用來存最後走過的節點順序（從終點往起點 push）。
### 步驟二： 加入邊的函數
```python=8
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u) # 無向圖要雙向加邊
```
### 步驟三： 檢查是否存在 Eulerian Path
```python=12
def has_eulerian_path(self):
odd = 0
for node in self.graph:
if len(self.graph[node]) % 2 != 0:
odd += 1
return odd == 0 or odd == 2
```
>遍歷每個節點，計算「度數是奇數的節點」數量。
若為 0 或 2 則符合尤拉路徑條件：
0：尤拉迴路（起點=終點）
2：尤拉路徑（兩端點度數為奇）
### 步驟四： 找合法起點
```python=19
def find_start_node(self):
for node in self.graph:
if len(self.graph[node]) % 2 != 0:
return node # 奇數度起點優先
return next(iter(self.graph)) # 否則任意一個
```
>如果有奇數度的節點，從其中一個開始。
否則隨便選一個點即可（因為是迴路型）。
### 步驟五： DFS 搜尋路徑 + 主流程
```python=19
def dfs(self, u):
while self.graph[u]:
v = self.graph[u].pop() # 拿一個鄰居
self.graph[v].remove(u) # 移除對邊（因為是無向圖）
self.dfs(v)
self.path.append(u)
def get_eulerian_path(self):
if not self.has_eulerian_path():
return []
start = self.find_start_node()
self.dfs(start)
return self.path[::-1] # 反轉得到正確順序
```
>`dfs()`：從起點 u 開始走訪所有邊，每條邊只走一次。
`pop()` 移除一條邊
走完後把 `u` 加入 `path`（這是「回溯」的時候做的）
`get_eulerian_path()`：整體流程控制，會回傳一條符合條件的完整路徑。
以下給一個`dfs()`例子:
:::spoiler 運行步驟（點我展開）
從 0 開始 DFS：
1. dfs(0)
graph[0] = [1, 3]
pop 1 → DFS(1)
2. dfs(1)
graph[1] = [2]
pop 2 → DFS(2)
3. dfs(2)
graph[2] = [3]
pop 3 → DFS(3)
4. dfs(3)
graph[3] = [0]
pop 0 → DFS(0)
5. dfs(0) again
graph[0] = [] → 無可走，append(0)
6.回到 dfs(3) → append(3)
7.回到 dfs(2) → append(2)
8.回到 dfs(1) → append(1)
9.回到最初 dfs(0) → append(0)
10.最後 path = [0, 3, 2, 1, 0]（要反轉）
:::
### 完整程式碼
>
```python=
from collections import defaultdict
class EulerianPath:
def __init__(self):
self.graph = defaultdict(list)
self.path = []
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u) # 無向圖，雙向加邊
def has_eulerian_path(self):
odd = 0
for node in self.graph:
if len(self.graph[node]) % 2 != 0:
odd += 1
return odd == 0 or odd == 2
def find_start_node(self):
for node in self.graph:
if len(self.graph[node]) % 2 != 0:
return node
return next(iter(self.graph))
def dfs(self, u):
while self.graph[u]:
v = self.graph[u].pop()
self.graph[v].remove(u) # 從另一邊也刪除
self.dfs(v)
self.path.append(u)
def get_eulerian_path(self):
if not self.has_eulerian_path():
return []
start = self.find_start_node()
self.dfs(start)
return self.path[::-1] # 反轉後就是正確順序
# 測試
if __name__ == "__main__":
ep = EulerianPath()
ep.add_edge(0, 1)
ep.add_edge(1, 3)
ep.add_edge(3, 0)
ep.add_edge(0, 4)
ep.add_edge(4, 3)
ep.add_edge(3, 2)
ep.add_edge(2, 5)
result = ep.get_eulerian_path()
if result:
print("Eulerian Path:", result)
else:
print("No Eulerian Path exists.")
```
> **Output**可能會有順序變化，這是其中一種
> ```
>Eulerian Path: [0, 4, 3, 0, 1, 3, 2, 5]
>```
## Eulerian Circuit
>以下圖為例
>
### 步驟一： 初始化類別與圖結構
```python=
from collections import defaultdict
class EulerianCircuit:
def __init__(self):
self.graph = defaultdict(list) # 鄰接表，用 list 存每個節點的鄰居
self.circuit = [] # 存放最終的 Eulerian Circuit 路徑
```
>使用 `defaultdict(list)`：若 key 不存在，自動建立空 list
`graph` 是無向圖的鄰接表
`circuit` 是最後存路徑用的 `list`（從終點回溯加入）
### 步驟二： 加入邊到圖中
```python=8
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u) # 因為是無向圖，兩邊都要加
```
>把節點 `u` 和 `v`之間加入邊
因為是無向圖，`graph[u]` 和 `graph[v]` 都要記錄
### 步驟三： 檢查是否符合 Eulerian Circuit 條件
```python=12
def is_eulerian_circuit(self):
for node in self.graph:
if len(self.graph[node]) % 2 != 0:
return False
return True
```
>所有節點的度數都必須是偶數
如果有任何一個點是奇數度，就直接回傳 `False`
### 步驟四： DFS 建構 Circuit 路徑
```python=18
def dfs(self, u):
while self.graph[u]:
v = self.graph[u].pop() # 拿一個鄰居 v
self.graph[v].remove(u) # 刪除對邊 (v, u)
self.dfs(v) # 遞迴走 v
self.circuit.append(u) # 回溯時加入路徑
```
>每次從當前點 `u` 出發，走訪並刪掉一條邊
走到底（無路可走）時，回溯把當前點加入路徑
最終 `self.circuit` 是「反向紀錄的路徑」，要反轉
### 步驟五： 主流程控制器，啟動 DFS
```python=25
def get_eulerian_circuit(self):
if not self.is_eulerian_circuit():
return []
start = next(iter(self.graph)) # 任選一個起點開始
self.dfs(start)
return self.circuit[::-1] # 回傳正確順序
```
>先檢查是否符合 Eulerian Circuit 條件
使用 `next(iter(...))` 拿一個起點
DFS 結束後，反轉 `circuit` 得到正確路徑
### 完整程式碼
>
```python=
from collections import defaultdict
class EulerianCircuit:
def __init__(self):
self.graph = defaultdict(list)
self.circuit = []
def add_edge(self, u, v):
self.graph[u].append(v)
self.graph[v].append(u)
def is_eulerian_circuit(self):
for node in self.graph:
if len(self.graph[node]) % 2 != 0:
return False
return True
def dfs(self, u):
while self.graph[u]:
v = self.graph[u].pop()
self.graph[v].remove(u)
self.dfs(v)
self.circuit.append(u)
def get_eulerian_circuit(self):
if not self.is_eulerian_circuit():
return []
start = next(iter(self.graph))
self.dfs(start)
return self.circuit[::-1]
# 測試主程式
if __name__ == "__main__":
ec = EulerianCircuit()
ec.add_edge(0, 1)
ec.add_edge(0, 2)
ec.add_edge(0, 3)
ec.add_edge(0, 4)
ec.add_edge(1, 5)
ec.add_edge(2, 5)
ec.add_edge(3, 4)
result = ec.get_eulerian_circuit()
print("Eulerian Circuit:" if result else "No Eulerian Circuit.")
print(result)
```
> **Output**可能會有順序變化，這是其中一種
> ```
>Eulerian Circuit:[0, 4, 3, 0, 2, 5, 1, 0]
>```
## Eulerian Circuit 、 Eulerian Path 程式碼差異
| 函式 | Path | Circuit |
| -------- | -------- | -------- |
| `has_eulerian_path()`| ✅ 有 0 或 2 奇數點| ❌ 沒有此檢查|
| `is_eulerian_circuit()`| ❌ 沒有此檢查 | ✅ 所有點度數都要偶數 |
| 起點選擇| 若有奇數 → 從奇數點開始 | 任意點即可 |
| 走法（DFS）| ✅ 一樣| ✅ 一樣|
| 結尾是否回原點 | ❌ 不一定| ✅ 必定回原點|
---
> 上一篇文章 [拓樸排序](https://hackmd.io/BeMu5-jOSre5GEGsbk3CmQ)
> 下一篇文章 [堆積排序](https://hackmd.io/HbcFW4cMTySYBFtzzowE9Q)
> 先備知識 無
> 延伸閱讀 無
Sign in with Wallet
Connect another wallet