---
# System prepended metadata

title: Euler路徑與Euler圖

---

# Euler路徑與Euler圖

> 上一篇文章　[拓樸排序](https://hackmd.io/BeMu5-jOSre5GEGsbk3CmQ)
> 下一篇文章　[堆積排序](https://hackmd.io/HbcFW4cMTySYBFtzzowE9Q)
> 先備知識   無
> 延伸閱讀   無
---

 # 概述
大家應該都聽過所謂的「一筆畫問題」，轉換成圖論版本就是：找到一條行跡（不重複
經過邊的路徑）使其經過一張圖上所有的邊。這就是所謂的「歐拉路徑」（Eulerianpath），
而如果要求起終點相同，就稱為「歐拉迴路」（Euleriancircuit）。

>下圖為範例圖
>![48727417-28c3d500-ec58-11e8-9715-33b168a50b7c](https://hackmd.io/_uploads/BJXyD6YZxg.png)


# 如何判斷圖是否可以形成Euler路徑與Euler圖

|      | Euler Circuit | Euler Path |
| -------- | -------- | -------- |
| 無向圖     | 圖中每個節點的邊的個數為偶數，且圖形需要聯通     | 所有點中，只有兩個點的邊的個數是奇數，且圖形需要聯通，或者符合無向圖的Euler Circuit|
| 有向圖    | 圖中每個節點進入邊的個數要等於出去邊的個數，且圖形需要聯通    | 所有點中只有一個點出去的邊個數多於進入的邊個數一個，且此點為起點。同時只有另一個點進入的邊個數多於出去的邊個數一個，此為終點。且圖形需要聯通，或者符合有向圖的Euler Circuit     |

# 程式實作

## Eulerian Path(無向圖)
>以下圖為例
>![螢幕擷取畫面 2025-05-20 172849](https://hackmd.io/_uploads/Hy3Pj6Fbex.png)

### 步驟一： 初始化圖的結構
```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()`例子:
![image](https://hackmd.io/_uploads/B16rFxh-lx.png)

:::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]（要反轉）
::: 

### 完整程式碼

>![螢幕擷取畫面 2025-05-20 172849](https://hackmd.io/_uploads/Hy3Pj6Fbex.png)


```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
>以下圖為例
>![螢幕擷取畫面 2025-05-22 092508](https://hackmd.io/_uploads/Bk43-Znble.png)

### 步驟一： 初始化類別與圖結構
```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` 得到正確路徑


### 完整程式碼

>![螢幕擷取畫面 2025-05-22 092508](https://hackmd.io/_uploads/r1LjJ-2-ex.png)
```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)
> 先備知識   無
> 延伸閱讀   無
