---
# System prepended metadata

title: 演算法 - 鮑興國

---

# 演算法 - 鮑興國

> 維護者：Vic Wen

### **排序演算法**
> 請自行學習各種排序 : )

| 排序演算法       | Big-Ω | Big-$\theta$ | Big-O | 穩定 | In-place |
|----------------|------------------|------------------|------------------|--------|---------------|
| 插入排序        | $O(n)$             | $O(n^2)$            | $O(n^2)$            | ✅    | ✅           |
| 選擇排序        | $O(n^2)$            | $O(n^2)$            | $O(n^2)$            | ❌  | ✅           |
| 氣泡排序        | $O(n)$             | $O(n^2)$            | $O(n^2)$            | ✅    | ✅           |
| 合併排序        | $O(nlogn)$       | $O(nlogn)$       | $O(nlogn)$       | ✅    | ❌ |
| 快速排序        | $O(nlogn)$       | $O(nlogn)$       | $O(n^2)$            | ❌  | ✅ |
| 堆積排序        | $O(nlogn)$       | $O(nlogn)$       | $O(nlogn)$       | ❌  | ✅           |
| 計數排序        | $O(n+k)$         | $O(n+k)$         | $O(n+k)$         | ✅    | ❌           |
| 基數排序        | $O(d(n+k))$            | $O(d(n+k))$            | $O(d(n+k))$            | ✅    | ❌   |

## Master Theorem

### **適用條件**
主定理適用於以下遞迴關係式：
$$
T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)
$$

- **a**：每次遞迴呼叫的子問題數量  
- **b**：每次遞迴呼叫將問題縮小的倍數  
- **f(n)**：合併子問題所需的額外成本  

---

### **三種情況：**

1. **分治成本主導**：  
如果 $f(n) = O(n^{d})$ 且 $d < \log_b a$  
$$
T(n) = \Theta\left(n^{\log_b a}\right)
$$
(分治成本大於合併成本)

2. **分治與合併成本平衡**：  
如果 $f(n) = \Theta(n^{d})$ 且 $d = \log_b a$  
$$
T(n) = \Theta\left(n^{d} \log n\right)
$$  
(分治成本與合併成本平衡)

3. **合併成本主導**：  
如果 $f(n) = \Omega(n^{d})$ 且 $d > \log_b a$  
若 $af(\frac{n}{b}) \leq cf(n)$ 對於某常數 $c < 1$ 成立  
$$
T(n) = \Theta(f(n))
$$  
(合併成本大於分治成本)

### **o-notation 與 ω-notation 簡介**

在演算法分析中，除了常見的 $O$ 符號 (Big O) 和 $\Omega$ 符號 (Big Omega) 之外，還有兩種較少使用但也很重要的符號：**$o$ 符號 (Little o)** 和 **$\omega$ 符號 (Little omega)**。它們表示更嚴格的上下界。

---

#### **1. $o$-notation (Little o notation)**
- **定義：**  
  $f(n) = o(g(n))$ 如果對於所有正數 $c > 0$，存在一個正整數 $n_0$，當 $n \geq n_0$ 時，都滿足：  
  $$
  0 \leq f(n) < c \cdot g(n)
  $$  
- **解釋：**  
  - $f(n)$ 的增長速率比 $g(n)$ 更慢。  
  - 換句話說，當 $n$ 趨近無窮大時，$f(n)$ 相對於 $g(n)$ 變得可以忽略不計。  
- **例子：**  
  $$
  n = o(n^2) \quad \text{因為對於任意 } c > 0, \quad n < c \cdot n^2 \quad \text{當 } n \text{ 足夠大}
  $$  
  $$
  \log n = o(n) \quad \text{因為對於任意 } c > 0, \quad \log n < c \cdot n \quad \text{當 } n \text{ 足夠大}
  $$  

---

#### **2. $\omega$-notation (Little omega notation)**
- **定義：**  
  $f(n) = \omega(g(n))$ 如果對於所有正數 $c > 0$，存在一個正整數 $n_0$，當 $n \geq n_0$ 時，都滿足：  
  $$
  0 \leq c \cdot g(n) < f(n)
  $$  
- **解釋：**  
  - $f(n)$ 的增長速率比 $g(n)$ 更快。  
  - 換句話說，當 $n$ 趨近無窮大時，$g(n)$ 相對於 $f(n)$ 變得可以忽略不計。  
- **例子：**  
  $$
  n^2 = \omega(n) \quad \text{因為對於任意 } c > 0, \quad c \cdot n < n^2 \quad \text{當 } n \text{ 足夠大}
  $$  
  $$
  n = \omega(\log n) \quad \text{因為對於任意 } c > 0, \quad c \cdot \log n < n \quad \text{當 } n \text{ 足夠大}
  $$  

---

### **o 與 O，ω 與 Ω 的差異**
| 符號   | 解釋                  | 嚴格性 |
| ------ | --------------------- | ------ |
| $O$  | 上界（可以相等）      | 寬鬆  |
| $o$  | 上界（必須嚴格小於）  | 嚴格  |
| $\Omega$ | 下界（可以相等）  | 寬鬆  |
| $\omega$ | 下界（必須嚴格大於）| 嚴格  |

---

#### **範例：**
- 插入排序的複雜度為 $O(n^2)$，而合併排序的複雜度為 $\Theta(n \log n)$，因此：  
  $$ 
  n \log n = o(n^2) \quad \text{因為 } n \log n \text{ 增長速率較慢}
  $$  
- 快速排序的最壞情況是 $O(n^2)$，但其平均情況是 $O(n \log n)$，因此：  
  $$
  n^2 = \omega(n \log n) \quad \text{因為 } n^2 \text{ 增長速率較快}
  $$  

### 1. Hash 表的概念
- **Hash 表 (Hash Table)** 是一種透過雜湊函數 (hash function) 將鍵值 (key) 映射到特定槽位 (slot) 的資料結構。
- 主要解決 **直接定址 (direct addressing)** 方法在面對龐大鍵值範圍時的空間浪費問題。
- 透過雜湊函數將龐大的鍵值範圍壓縮成較小的表格大小。

---

### 2. 雜湊函數 (Hash Function)
- 將鍵值 $k$ 映射到範圍 $0, 1, \dots, m - 1$ 中的某個槽位 (slot)。
- 常見雜湊函數方法：
  - **除法法 (Division Method)**: $h(k) = k \mod m$
      - $m$ 應該是質數，且接近2的冪但不為冪數，如 $2^p - 1$
  - **乘法法 (Multiplication Method)**: $h(k) = \lfloor m (kA \mod 1) \rfloor$
      - $A$ 常選為不規則數值，如 $\frac{sqrt(5)-1}{2} ≈ 0.6180339887$ (Knuth建議)
      - m 應該為 $2^p$，這樣可以快速取模。

---

### 3. 碰撞解決方法 (Collision Resolution)
#### 3.1 鏈結法 (Chaining)
- 將相同槽位的所有元素存於一個鏈結串列 (linked list) 中。
- **操作效率**：
  - 插入：$O(1)$（假設插入在鏈結串列的頭部）
  - 搜尋：$O(1 + \alpha)$（$\alpha$ 為載入因子）
  - 刪除：$O(1)$（若為雙向鏈結串列）
- **載入因子 (Load Factor)**：$\alpha = \frac{n}{m}$ (n: 元素總數, m: slot 數量)

#### 3.2 開放定址法 (Open Addressing)
- 將所有元素直接存放在哈希表中，無法使用鏈結。
- 常見方法：
  - **線性探測 (Linear Probing)**：$h(k, i) = (h(k) + i) \mod m$
      - 容易產生**主要聚集 (Primary Clustering)**，連續槽位衝突。
  - **二次探測 (Quadratic Probing)**：$h(k, i) = (h(k) + c_1i + c_2i^2) \mod m$
      - 產生**次要聚集 (Secondary Clustering)**。
  - **雙重雜湊 (Double Hashing)**：$h(k, i) = (h_1(k) + i \times h_2(k)) \mod m$

---

### 4. 開放定址法的分析
- **線性探測**：
- **二次探測**：避免主要聚集但可能
- **雙重雜湊**：有效降低聚集問題，接近均勻雜湊。

#### 4.1 搜尋效率
- **不成功搜尋**：$O(\frac{1}{1 - \alpha})$
- **成功搜尋**：$O(1 + \frac{1}{1 - \alpha})$

---

### 5. 雜湊表的特性
- **效率**：在理想情況下，搜尋、插入、刪除的時間複雜度為 $O(1)$。
- **適用場合**：當鍵值範圍很大但實際使用鍵值數量較少時，雜湊表是一種高效的解決方案。

---

### 6. 設計良好雜湊表的原則
- 使用**質數大小**的表格長度 $m$，避免槽位重疊。
- 選擇合適的雜湊方法和碰撞解決技術，根據數據特性進行優化。
- **負載因子**不宜過高，通常控制在 $0.5 \sim 0.75$。

## ---- 期末考分隔線 ---

## Dynamic Programming
* `MATRIX-CHAIN-ORDER` 
    * 是 **Bottom-Up** 填表格。
    * 時間複雜度：$O(n^3)$
    * 空間複雜度：$\theta(n^2)$
* `MEMOIZED-MATRIX-CHAIN` 
    * 是 **Top-Down** 遞迴加上儲存。
    * 時間複雜度：$O(n^3)$
    * 空間複雜度：$\theta(n^2)$


### MATRIX-CHAIN-ORDER

`MATRIX-CHAIN-ORDER` 是求解「矩陣鏈乘法最佳括號化順序」的 **Bottom-Up 動態規劃演算法**，可有效避免重複子問題的計算


```plaintext
MATRIX-CHAIN-ORDER(p)
1. n ← length[p] – 1
2. for i ← 1 to n
3.     m[i, i] ← 0                     // 單一矩陣不需要乘法
4. for l ← 2 to n                     // l 是鏈長
5.     for i ← 1 to n – l + 1
6.         j ← i + l – 1
7.         m[i, j] ← ∞
8.         for k ← i to j – 1
9.             q ← m[i, k] + m[k+1, j] + p[i–1] * p[k] * p[j]
10.            if q < m[i, j]
11.                m[i, j] ← q
12.                s[i, j] ← k         // 記下括號切割點
13. return m and s
```

---

#### 🧠 說明細節

* `m[i][j]`：Aᵢ × Aᵢ₊₁ × ⋯ × Aⱼ 的**最小乘法成本**
* `s[i][j]`：從哪個位置 k 切開，才能得到最佳解
* 第 4 行：先從鏈長度 2 開始計算，慢慢增長至整串矩陣
* 第 9 行：核心遞推公式：
  $$
  m[i, j] = \min_{i \le k < j} \left\{ m[i, k] + m[k+1, j] + p_{i-1} \cdot p_k \cdot p_j \right\}
  $$

![image](https://hackmd.io/_uploads/rJos54Mblx.png)


若輸入矩陣維度為：

```plaintext
p = [30, 35, 15, 5, 10, 20, 25]
```

代表矩陣：

* A₁: 30×35
* A₂: 35×15
* A₃: 15×5
* A₄: 5×10
* A₅: 10×20
* A₆: 20×25

---

#### 🔁 如何回推出括號（PRINT-OPTIMAL-PARENS）

利用 `s[i][j]` 回推最優括號方式：

```plaintext
PRINT-OPTIMAL-PARENS(s, i, j)
1   if i == j
2       print "A" + i
3   else
4       print "("
5       PRINT-OPTIMAL-PARENS(s, i, s[i][j])
6       PRINT-OPTIMAL-PARENS(s, s[i][j] + 1, j)
7       print ")"
```

---

### MEMOIZED-MATRIX-CHAIN

時間複雜度：$O(n^3)$
空間複雜度：$\theta(n^2)$

是一種使用 **備忘錄法（Memoization）** 的 **動態規劃解法**，用來解決 `RECURSIVE-MATRIX-CHAIN` 因重複計算造成效率低落的問題。


這個方法保留一個表格 `m[i][j]`，用來記錄子問題 Aᵢ..Aⱼ 的最佳乘法次數。如果之前已經計算過，就直接回傳，不再重複遞迴。


```plaintext
MEMOIZED-MATRIX-CHAIN(p)
1.  n ← length[p] – 1
2.  for i ← 1 to n
3.      for j ← i to n
4.          m[i, j] ← ∞
5.  return LOOKUP-CHAIN(p, 1, n)
```

```plaintext
LOOKUP-CHAIN(p, i, j)
1.  if m[i, j] < ∞
2.      then return m[i, j]
3.  if i = j
4.      then m[i, j] ← 0
5.  else
6.      for k ← i to j – 1
7.          q ← LOOKUP-CHAIN(p, i, k) 
              + LOOKUP-CHAIN(p, k+1, j) 
              + p[i–1] * p[k] * p[j]
8.          if q < m[i, j]
9.              then m[i, j] ← q
10. return m[i, j]
```

#### 遞迴說明：

* **第1–2行**：如果之前計算過 `m[i][j]`，就直接回傳，避免重複。
* **第3–4行**：當 `i = j`，只是一個矩陣，乘法次數為 0。
* **第6–9行**：列舉所有分割點 `k`，計算最小乘法次數，並儲存在 `m[i][j]` 中。
* **第10行**：回傳 `m[i][j]` 的最小值。

![image](https://hackmd.io/_uploads/H1FnqEM-lx.png)

### LCS - Longest Common Subsequence

**輸入：**
兩個字元序列（字串）：

* X = ⟨x₁, x₂, ..., xₘ⟩
* Y = ⟨y₁, y₂, ..., yₙ⟩

**輸出：**
一個最長的子序列（可不連續，但**順序需一致**），同時是 X 和 Y 的子序列。


#### 1. 定義子問題
* `c[i][j]`：表示 X\[1..i] 和 Y\[1..j] 的 LCS 長度
* `b[i][j]`：紀錄方向，用於回推路徑

---

#### 2. 遞推公式

對所有 i = 1..m，j = 1..n：

$$
c[i][j] = 
\begin{cases}
0 & \text{if } i = 0 \text{ or } j = 0 \\
c[i-1][j-1] + 1 & \text{if } x_i = y_j \\
\max(c[i-1][j], c[i][j-1]) & \text{if } x_i \ne y_j
\end{cases}
$$

> 白話文：相同取左斜上，不相同取 max(左, 上)

---

#### 3. Pseudocode

```plaintext
LCS-LENGTH(X, Y)
1. m ← length[X]
2. n ← length[Y]
3. for i ← 0 to m
4.     c[i][0] ← 0
5. for j ← 0 to n
6.     c[0][j] ← 0
7. for i ← 1 to m
8.     for j ← 1 to n
9.         if X[i] == Y[j]
10.            c[i][j] ← c[i-1][j-1] + 1
11.            b[i][j] ← "↖"
12.        else if c[i-1][j] ≥ c[i][j-1]
13.            c[i][j] ← c[i-1][j]
14.            b[i][j] ← "↑"
15.        else
16.            c[i][j] ← c[i][j-1]
17.            b[i][j] ← "←"
18. return c and b
```

---

#### 4. 回推輸出結果：PRINT-LCS

```plaintext
PRINT-LCS(b, X, i, j)
1. if i == 0 or j == 0
2.     return
3. if b[i][j] == "↖"
4.     PRINT-LCS(b, X, i-1, j-1)
5.     print X[i]
6. else if b[i][j] == "↑"
7.     PRINT-LCS(b, X, i-1, j)
8. else
9.     PRINT-LCS(b, X, i, j-1)
```


#### 範例

X = ⟨A, B, C, B, D, A, B⟩
Y = ⟨B, D, C, A, B, A⟩

LCS 可能為：`BCBA` 或 `BDAB`

#### 複雜度分析

| 項目         | 複雜度      |
| ---------- | -------- |
| Find LCS      | $O(mn)$ |
| Print LCS | $O(m + n)$ |


#### 特性

* **Optimal Substructure**：子問題的最優解構成全體的最優解
* **Overlapping Subproblems**：`c[i][j]` 常被重複查詢，適合 DP 解法

## Greedy

### A-S problem (Activity-Selection Problem)

給定一組活動，每個活動都有開始時間 $s_i$ 與結束時間 $f_i$。所有活動共享一個資源（例如一個教室），任兩個活動不能重疊。目標是**選出最多個不重疊的活動**。

#### 輸入：

* 一組活動 $A = \{a_1, a_2, ..., a_n\}$
* 每個活動 $a_i$ 有對應的開始時間 $s_i$ 和結束時間 $f_i$，其中 $s_i < f_i$

#### 輸出：

* 一組最大的不相交活動集合 $S \subseteq A$，使得集合中的活動互不重疊

#### 🧩 範例

| 活動編號 | 開始時間 $s_i$ | 結束時間 $f_i$ |
| ---- | ---------- | ---------- |
| A1   | 1          | 4          |
| A2   | 3          | 5          |
| A3   | 0          | 6          |
| A4   | 5          | 7          |
| A5   | 3          | 8          |
| A6   | 5          | 9          |
| A7   | 6          | 10         |
| A8   | 8          | 11         |
| A9   | 8          | 12         |
| A10  | 2          | 13         |
| A11  | 12         | 14         |

最佳選擇：
$A1 → A4 → A8 → A11$（共 4 個活動）

#### 貪心策略（Greedy Strategy）

每次選擇**最早結束的活動**，然後**刪除與其衝突的其他活動**，再重複進行。

* 選擇最早結束的活動可讓剩下的時間空間最大化
* 保證最多能容納後續活動

#### 演算法步驟（Activity-Selection-Greedy）

1. 將所有活動依照結束時間 $f_i$ 升序排序
2. 初始化選擇集合 S = {第一個活動}
3. 記錄上一個選擇的活動 $a_{last}$
4. 對每個活動 $a_i$ 從第二個開始：
     如果 $s_i$ ≥ $f_{last}$
         將 $a_i$ 加入 $S$
         更新 $f_{last}$ = $f_i$
5. 輸出 $S$

---

#### 正確性證明（Greedy Choice Property & Optimal Substructure）

* 假設有最早結束的活動 $a_1$，與一個最優解 $O$ 不同。
* 可以證明，若將 $O$ 中第一個活動換成 $a_1$，仍是一個合法解。
* 此步驟可以持續套用，直到所有選擇與貪心策略一致。

#### **最適子結構（Optimal Substructure）**

* 在排除與第一個被選中活動衝突的活動後，**剩下的子問題仍是原來的問題結構**。
* 可遞迴解決每個子問題。


##### 符號定義

* **$c[i, j]$**：對於子問題 $S_{ij}$，其對應的最優解「代價」。
* **$S_{ij}$**：代表從第 $i$ 個元素到第 $j$ 個元素的子集合，或者是某個結構（例如區間、節點）的子範圍。

這條公式：

$$
c[i, j] = c[i, k] + c[k, j] + 1
$$

意思是：若要解決區間 $[i, j]$，可以透過在某個中間點 $k$ 拆解為左子區間 $[i, k]$ 與右子區間 $[k, j]$，而「+1」代表進行這次分割或合併的代價。


##### 遞迴關係式（Recurrence）

$$
c[i, j] = 
\begin{cases}
0 & \text{if } S_{ij} = 0 \\
\max_{i < k < j} \{ c[i, k] + c[k, j] + 1 \} & \text{if } S_{ij} \neq 0
\end{cases}
$$

解釋如下：

* 若 $S_{ij}$ 是空集合，即無元素可選（例如 $j \leq i+1$），則代價為 0。
* 否則，試圖在 $i < k < j$ 的每一個中間點上拆分，選出讓總成本最大的方式（這裡是取 `max`，也可能視問題為 `min`）。

雖然這個遞迴關係式 **可以理論上定義出最優解**，但實際上該問題會用 **Greedy（貪心）演算法** 來解，因為它具有貪心選擇性與最適子結構。

#### A Recursive Greedy Algorithm

```
RECURSIVE-ACTIVITY-SELECTOR(s, f, i, n):
    1. m ← i + 1
    2. while m ≤ n and s[m] < f[i]        ← 找第一個與 a_i 不衝突的活動
          m ← m + 1
    3. if m ≤ n
          return {a_m} ∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m, n)
       else
          return 0
```

![image](https://hackmd.io/_uploads/H1fzZRGWel.png)

### Elements of the greedy strategy

#### 1. **Greedy Choice Property（貪心選擇性）**

* **定義**：可以藉由做出當前局部最好的選擇，來達成整體最優解。
* 換句話說，不需要回溯或考慮所有可能的組合，只要一步步做出當下最好的決定即可。

**例子：** 在活動選擇問題（Activity Selection）中，選擇**最早結束**的活動可以讓我們保留最多可用時間去選其他活動。

#### 2. **Optimal Substructure（最適子結構）**

* **定義**：一個問題的最優解可以由其子問題的最優解組成。
* 貪心演算法也需要此性質，這與動態規劃相同。
* 但不同的是，貪心法只選一次（不記憶所有子問題解），而動態規劃會儲存所有子問題結果。

例子：在最小生成樹（如 Kruskal’s Algorithm）中，任何子樹也應是最小生成樹的一部分。

#### 3. **Candidate Set（候選集合）**

* 所有可選的元素的集合。
* 貪心演算法會從這個集合中依據某種準則（如成本最小）選擇一個元素。

例子：在 Huffman 編碼中，候選集合是尚未合併的節點（依照頻率排序）。

#### 4. **Selection Function（選擇函數）**

* 定義如何從候選集合中選擇當前看起來最好的元素。
* 通常是選擇最大值、最小值、最早或最短等。

例子：在 Dijkstra 演算法中，選擇當前未訪問節點中距離起點最近的節點。

#### 5. **Feasibility Check（可行性檢查）**

* 檢查當前選擇是否仍符合問題的限制條件。
* 若選擇後導致解不合法，就跳過此候選項。

**例子：** 在背包問題中，選擇物品之前需確認不超過背包容量。

#### 6. **Solution Set（解集合）**

* 一個逐步累積的集合，代表目前所構造出的部分解。
* 每選一項就加入解中，直到不能再選或完成整個問題。

---

#### 判斷是否可用貪心法的核心

* 問題是否具有 **貪心選擇性**？
* 問題是否具有 **最適子結構**？
* 是否能定義一個明確的「選擇策略」並保證其正確性？

若答案都是「是」，那就可以設計一個有效的貪心演算法。

| 要素名稱                 | 說明              | 舉例         |
| -------------------- | --------------- | ---------- |
| Greedy Choice        | 每步選局部最優         | 活動選擇問題     |
| Optimal Substructure | 最佳解由子問題的最佳解組成   | 最小生成樹      |
| Candidate Set        | 所有可選元素          | 所有活動、邊、物品等 |
| Selection Function   | 根據準則選出最優候選      | 最早結束、最低花費  |
| Feasibility Check    | 是否合法（不衝突、不超容量等） | 不重疊活動、背包容量 |
| Solution Set         | 持續累積的最終解構造      | 已選活動、邊、物品  |


### 與 DP 的比較


| 特色         | 動態規劃（DP）                                                 | 貪婪演算法（Greedy）                                             |
| ---------- | -------------------------------------------------------- | --------------------------------------------------------- |
| **最適子結構**  | 必要條件：原問題的最優解由所有子問題最優解組合而成。                               | 必要條件：與 DP 相同，但還要滿足「Greedy Choice Property 貪婪選擇性質」。                               |
| **重疊子問題**  | 需要：存在大量重複子問題，適合以「備忘錄」或「表格填表」方式。                          | 不需要：每一步只看「局部資訊」，不必重複計算子問題。                                |
| **貪婪選擇性質** | 不要求：DP 可以在最後以遞迴或迴圈從頭到尾檢查各方案。                             | 必須：每次做出「最佳局部選擇」，保證剩餘子問題仍可最優。                              |
| **計算方式**   | 自底而上（bottom‐up）或自頂而下（top‐down），全盤考慮子問題。                  | 自頂而下，每步直接做局部最優，不回頭。                                       |
| **時間複雜度**  | 通常較高（多項式時間），因為要枚舉大量子問題。                                  | 通常較低（線性或線性對數），只要做幾次排序或迴圈就行。                               |
| **適用問題範例** | 背包問題（Knapsack）、最長公共子序列（LCS）、最短路徑（Dijkstra/Bellman‐Ford）。 | 活動選擇（Activity Selection）、Huffman 編碼、最小生成 樹（Prim/Kruskal）。 |


### Knapsack Problems

> 沒細講具體實現

$$
\max \sum_i x_i v_i
$$

* 選擇物品的數量 $x_i$
* 每個物品的價值是 $v_i$
* 目標是**最大化總價值**

#### 限制條件：

$$
\sum_i x_i w_i \leq W
$$

* 每個物品的重量是 $w_i$
* $W$ 是背包容量
* **總重量不能超過容量**

#### 1. **0-1 Knapsack Problem（0-1背包問題）**

* $x_i \in \{0,1\}$：每個物品**只能選或不選**
* **不可切割**
* 必須使用 **動態規劃 (dp)** 解決，無法用貪心法
* 是 **NP-complete 問題**

##### 解法提示：

* 二維 DP：`dp[i][w]` = 前 $i$ 項中容量為 $w$ 時的最大價值
* 一維優化：滾動陣列 `dp[w]`

---

#### 2. **Fractional Knapsack Problem（可分割背包問題）**

* $x_i \in [0,1]$：每個物品可以**取任意比例**
* **可切割**
* 可以使用 **貪心演算法（Greedy Algorithm）**
* 具有「**貪心選擇性**」與「**最適子結構**」

##### 解法策略：

* 計算所有物品的價值密度 $\frac{v_i}{w_i}$
* 依照密度降序排列
* 儘可能選取密度最高的物品直到背包裝滿

##### 總結

| 類型                  | 可分割 | 演算法   | 是否貪心適用 | 複雜度           |
| ------------------- | --- | ----- | ------ | ------------- |
| 0-1 Knapsack        | 否   | 動態規劃  | ❌ 否    | $O(nW)$       |
| Fractional Knapsack | 是   | 貪心演算法 | ✅ 是    | $O(n \log n)$ |

### Huffman Codes 

$O(nlogn)$




```
HUFFMAN( C )
1	n ← |C|
2	Q ← C
3	for  i ← 1 to  n – 1 
4		do allocate a new node z
5		     z.left ← x ← EXTRACT-MIN(Q)
6		     z.right[z] ← y ← EXTRACT-MIN(Q)
7		     z.freq ← x.freq + y.freq
8		     INSERT(Q, z)
9	return EXTRACT-MIN(Q)
```

![image](https://hackmd.io/_uploads/ryQRLRz-lx.png)

![image](https://hackmd.io/_uploads/BkgrUCfbge.png)


#### Fixed-length v.s. Variable-length

##### 🎯 目標與設計動機

| 類型                          | 常見用途             | 設計動機              |
| --------------------------- | ---------------- | ----------------- |
| Fixed-length                | 記憶體存取、編譯器、簡單資料結構 | 計算簡單、容易存取         |
| Variable-length (如 Huffman) | 壓縮、傳輸協定、影像壓縮等    | 節省空間，依據符號頻率最佳化總長度 |


##### ⚙️ 技術實作上的差別

| 類別              | 優點              | 缺點                         |
| --------------- | --------------- | -------------------------- |
| Fixed-length    | 快速索引（直接定位）、實作簡單 | 編碼空間浪費（不能依照頻率最佳化）          |
| Variable-length | 空間效率高（接近熵下限）    | 需要額外資料結構或 prefix-free 性質解碼 |

##### 比較表

| 特性             | Fixed-length | Variable-length |
| -------------- | ------------ | --------------- |
| 每個字元長度         | 相同           | 不同              |
| 是否 prefix-free | 自動           | 需設計（如 Huffman）  |
| 壓縮效率           | 通常較差         | 通常較好            |
| 計算與實作難度        | 較簡單          | 較複雜（需樹或表）       |
| 解碼方式           | 可直接索引        | 須從位元流逐位解讀       |

* **Fixed-length** 適合：

  * 快速查表（如字元轉換、硬體編址）
  * 字元數量固定且均勻的場景

* **Variable-length** 適合：

  * **資料壓縮**（如 Huffman、Arithmetic Coding）
  * 頻率差異大、需要節省儲存或頻寬的場景

#### 總成本

$$
B(T) = \sum_{c \in C} c.\text{freq} \cdot d_T(c)
$$

#### 符號說明：

| 符號              | 意義                                |
| --------------- | --------------------------------- |
| $B(T)$          | 這棵編碼樹 $T$ 的總成本（**加權路徑長度**）        |
| $C$             | 符號集合（character set）               |
| $c.\text{freq}$ | 字元 $c$ 出現的頻率（可視為機率）               |
| $d_T(c)$        | 在編碼樹 $T$ 中，字元 $c$ 對應的葉節點深度（即編碼長度） |

#### 意義與應用：

* **這是 Huffman 演算法要最小化的目標函數。**
* 它表示編碼整個輸入資料所需的 **總位元數**，考慮了：
  * 字元出現的頻率
  * 每個字元在編碼樹中的深度（即其二進位碼的長度）

#### 舉例

假設有：

| 字元 | 頻率 | 編碼   | 深度 |
| -- | -- | ---- | -- |
| A  | 5  | 1100 | 4  |
| B  | 9  | 1101 | 4  |
| F  | 45 | 0    | 1  |

部分總成本為：

$$
B(T) = 5 \cdot 4 + 9 \cdot 4 + 45 \cdot 1 = 20 + 36 + 45 = 101
$$

→ 此為這三個字元在該樹中的貢獻成本。

---

#### 目標

就是構造一棵二元樹 $T$，使得：

$$
\boxed{B(T) \text{ 最小化}}
$$

這就是為什麼 Huffman 編碼過程中：
* 總是合併**頻率最小的兩個節點**
* 保證這兩個最不重要的符號放在**最深的層**，以節省整體位元總數

#### 與壓縮有什麼關係？

* 壓縮比（compression ratio）與 $B(T)$ 成正比
* $B(T)$ 越小 → 平均每個字元用的位元越少 → 壓縮效果越好
* 若搭配輸入總長度 $N$，實際位元數為 $N \cdot \text{平均碼長}$

---

### 證明

$$
B(T) - B(T') = \sum_{c \in C} c.\text{freq} \cdot d_T(c) - \sum_{c \in C} c.\text{freq} \cdot d_{T'}(c)
$$

> 若我們將兩個最低頻率的符號 $x$ 和 $a$ 作為最深層的葉節點，則總加權成本 $B(T)$ 不會變差，甚至更好。

#### 🔍 符號與定義：

| 符號              | 意義                                 |
| --------------- | ---------------------------------- |
| $T$             | 原本的編碼樹                             |
| $T'$            | 經過「交換」後的新樹                         |
| $c \in C$       | 字元集合中的任意字元                         |
| $x, a \in C$    | 頻率最低的兩個字元（Huffman 選來合併的）           |
| $d_T(c)$        | 在樹 $T$ 中，字元 $c$ 的深度                |
| $c.\text{freq}$ | 字元 $c$ 的頻率                         |
| $B(T)$          | 編碼樹 $T$ 的總成本（Weighted Path Length） |


由於只有 $x$ 和 $a$ 的位置交換，其餘符號深度不變，所以其他項目抵銷，只剩下：


$$
= x.\text{freq} \cdot d_T(x) + a.\text{freq} \cdot d_T(a) - x.\text{freq} \cdot d_{T'}(x) - a.\text{freq} \cdot d_{T'}(a)
$$

若交換後 $x$ 和 $a$ 的深度互換，則有：

$$
d_{T'}(x) = d_T(a), \quad d_{T'}(a) = d_T(x)
$$

所以代入變成：

$$
= x.\text{freq} \cdot d_T(x) + a.\text{freq} \cdot d_T(a) - x.\text{freq} \cdot d_T(a) - a.\text{freq} \cdot d_T(x)
$$

整理：

$$
= (a.\text{freq} - x.\text{freq})(d_T(a) - d_T(x))
$$


##### 為何這個乘積一定大於等於 0？

因為：

* 假設 $a$ 的頻率比較大 → $a.\text{freq} > x.\text{freq}$
* 同時 $x$ 在較深層 → $d_T(a) > d_T(x)$

所以：

* $a.\text{freq} - x.\text{freq} > 0$
* $d_T(a) - d_T(x) > 0$

⇒ 他們的乘積必定非負：

$$
\boxed{B(T) - B(T') \geq 0}
$$

即：這次交換不會讓總成本更糟，甚至可能讓它更好。

---

##### 為什麼這麼做有意義？

這個推導支撐了 Huffman 演算法的**核心正確性原則**：

> **「最低頻率的字元應該放在最深層」**

這樣才能使最深的（長度最長的）路徑配給頻率最小的字元，從而**最小化總加權成本 $B(T)$**。

---

##### 結論

這個引理證明了：

* Huffman 每次選擇頻率最低的兩個項目來合併，是一個**貪心且不會錯的選擇**
* 若不是這樣做，總有一種「交換」方法可以讓樹的成本更好或一樣
* 這就是貪心策略的正確性依據

---

### 證明

> 證明 Huffman 演算法每次合併 $x$ 與 $y$ 的操作，其對整體加權路徑長度 $B(T)$ 的貢獻是：

$$
x.\text{freq} \cdot d_T(x) + y.\text{freq} \cdot d_T(y)
= z.\text{freq} \cdot d_{T'}(z) + (x.\text{freq} + y.\text{freq})
$$

---

#### 🔍 證明逐步說明

##### Step 1：起始狀態

原本樹中有：

* 左子節點 $x$，深度 $d_T(x)$
* 右子節點 $y$，深度 $d_T(y)$

總成本貢獻是：

$$
x.\text{freq} \cdot d_T(x) + y.\text{freq} \cdot d_T(y)
$$

---

##### Step 2：將 $x$ 和 $y$ 合併成新節點 $z$

* 在新樹 $T'$ 中，$z$ 的深度為 $d_{T'}(z)$
* 因為 $x$ 與 $y$ 是 $z$ 的子節點，故：

$$
d_T(x) = d_{T'}(z) + 1,\quad d_T(y) = d_{T'}(z) + 1
$$

---

##### Step 3：代入上式

$$
x.\text{freq} \cdot (d_{T'}(z) + 1) + y.\text{freq} \cdot (d_{T'}(z) + 1)
$$

合併整理：

$$
(x.\text{freq} + y.\text{freq}) \cdot (d_{T'}(z) + 1)
$$

---

##### Step 4：引入 $z$ 的頻率

* $z.\text{freq} = x.\text{freq} + y.\text{freq}$
* 展開乘法：

$$
z.\text{freq} \cdot d_{T'}(z) + z.\text{freq}
$$

也就是：

$$
z.\text{freq} \cdot d_{T'}(z) + (x.\text{freq} + y.\text{freq})
$$

---

##### 📌 結論與意義

這項推導說明了：

* 在 Huffman 樹的構造過程中，**每次合併的成本可以明確拆解為兩部分**：

  1. 新內部節點 $z$ 的路徑成本：$z.\text{freq} \cdot d(z)$
  2. 額外的“+1”貢獻：因為每個子節點深度都比原先多 1


## Disjoint Sets

是一種用來管理一組不重疊集合的資料結構，支援以下三個操作：

* **MAKE-SET(x)**：建立一個新集合，元素為 x。
* **FIND-SET(x)**：找出包含 x 的集合代表元素（通常是根節點）。
* **UNION(x, y)**：合併包含 x 與 y 的兩個集合。

### Connected Components

```plaintext
CONNECTED-COMPONENTS(G)
for each vertex v in V[G]
    do MAKE-SET(v)
for each edge (u, v) in E[G]
    do if FIND-SET(u) ≠ FIND-SET(v)
        then UNION(u, v)
```

這樣能夠將所有連通的節點合併在同一個集合裡，完成連通元件的分析。

![image](https://hackmd.io/_uploads/H1Sx30GZlx.png)


---

### 三、資料結構實作

#### 1. Linked List 實作

* 每個集合用一個 linked list 表示。
* 儲存 head/tail 方便合併。
* UNION 的效率為 $O(n)$，因為要更新整個鏈結串列中的 pointer。
* 每個節點儲存：
  * 自身值 `x`
  * 指向集合代表元素的指標 `x.rep`
* 每個集合儲存：
  * 頭尾指標 `head`、`tail`
  * 節點數量（可選）

![image](https://hackmd.io/_uploads/B1D9s2UZxx.png)


##### 1. MAKE-SET(x) - $O(1)$

建立一個只包含 `x` 的新集合：

```text
x.rep ← x
x.next ← NIL
head ← tail ← x
```

##### 2. FIND-SET(x) - $O(1)$

只需回傳 `x.rep`


##### 3. UNION(x, y) - $O(n)$

合併兩個集合，令 `x` 所在集合為 A，`y` 所在集合為 B：

1. **將 B 的串列接到 A 的尾端**
2. **更新 B 中每個節點的 rep 指標為 A 的 head**
3. **更新 tail 指標**

> 因為必須遍歷整個集合 B，逐一更新其每個元素的 `rep`


##### 📉 效能問題

* `FIND-SET` 是 **O(1)**
* `MAKE-SET` 是 **O(1)**
* `UNION` 是 **O(n)**，當集合很大時效率低落

因此，在實務中通常會採用 **Disjoint-set Forest + Union by Rank + Path Compression**，可達到「近乎常數時間」操作。

---

### Weighted Union Heuristic

當合併兩棵集合的樹時，**讓小的集合指向大的集合**。

* 小集合：節點數量較少
* 大集合：節點數量較多

這樣可以避免形成「一條長鏈」，保持整體樹的高度低。

#### 結構設計

每個集合的根節點記錄一個整數 `size`（或 rank），代表集合中元素的數量。

#### 🔧 操作流程

##### `MAKE-SET(x)`

* 建立一棵新樹，大小為 1：

```plaintext
x.parent = x
x.size = 1
```
##### `FIND-SET(x)`

* 找出樹的根節點
* （可搭配 Path Compression）

##### `UNION(x, y)`

```plaintext
xr = FIND-SET(x)
yr = FIND-SET(y)
if xr == yr:
    return

if xr.size < yr.size:
    xr.parent = yr
    yr.size += xr.size
else:
    yr.parent = xr
    xr.size += yr.size
```

若只使用 **Weighted Union（加權合併）** 而不搭配 Path Compression：

* 單次操作為 $O(\log n)$
* 因為最壞情況下，每次合併至少讓一棵樹的大小翻倍 ⇒ 樹高最多為 $\log n$

但如果搭配 **Path Compression**：

* $m$ 次操作總時間複雜度為：

$$
\mathcal{O}(m \cdot \alpha(n))
$$

其中 $\alpha(n)$ 是反 Ackermann 函數，增長極慢，幾乎視為常數。

| 項目    | 說明                                 |
| ----- | ---------------------------------- |
| 減少樹高  | 最小化後續查找時間                          |
| 保證效率  | 即使不搭配 Path Compression，仍是 O(log n) |
| 搭配最佳化 | 與 Path Compression 合用，可達到幾乎常數時間    |


---


#### 2. Disjoint-set Forests（森林）

* 每個集合用一棵樹表示。
* FIND-SET：循著 parent pointer 找到根節點。
* MAKE-SET(x)：將 x 自成一樹，x.p = x。
* UNION(x, y)：將一棵樹的根接到另一棵樹上。



---

### 四、效能優化技巧

#### 1. Union by Rank（秩合併）

* 將秩（rank）小的樹合併到秩大的樹，減少樹高。
* 若秩相等，合併後根節點的秩 +1。

rank[x] 不是節點數，也不是確切高度，而是：**「x 所在子樹的高度上界（upper bound on height）」**

初始化時：MAKE-SET(x) 會設 rank[x] = 0。

#### 2. Path Compression（路徑壓縮）

* 在 FIND-SET 過程中，將訪問過的節點直接接到根節點，壓縮路徑。
* 這不會改變 rank，但能顯著加速 FIND。

---

### 五、操作程式碼 (Pseudocode)

```plaintext
MAKE-SET(x)
    x.p = x
    x.rank = 0

FIND-SET(x)
    if x ≠ x.p
        x.p = FIND-SET(x.p)
    return x.p

LINK(x, y)
    if x.rank > y.rank
        y.p = x
    else
        x.p = y
        if x.rank == y.rank
            y.rank = y.rank + 1

UNION(x, y)
    LINK(FIND-SET(x), FIND-SET(y))
```

---

### 六、效能分析

當 **Union by Rank** 和 **Path Compression** 同時使用時，操作的時間複雜度趨近於 **α(n)**（Ackermann 函數的反函數，極慢增長），可視為常數時間。

---

在使用「**union by rank**」與「**path compression**」的 **disjoint-set forest** 中，
若進行總共 $m$ 次操作（包括 `MAKE-SET`, `UNION`, `FIND-SET`），其中 $n$ 次是 `MAKE-SET`，
總時間複雜度為：

$$
\mathcal{O}(m \cdot \alpha(n))
$$

其中 $\alpha(n)$ 是反 Ackermann 函數，**極慢增長**（對所有實際應用可視為常數）。

> 問題：這會讓排序更快嗎？

❌ 答案：**不會**。

#### 1. **比較排序的下限依然存在**

在「決策樹模型 (decision tree model)」下，所有基於比較的排序法都存在下限：

$$
\Omega(n \log n)
$$

這是因為對 $n$ 個元素有 $n!$ 種排列，而需要至少 $\log_2(n!) = \Omega(n \log n)$ 次比較才能唯一確定排序結果。

即使 Disjoint Set 的某些操作是 "近乎常數"，**排序還是得比較元素大小**，而這個步驟不能被 Disjoint Set 取代。

---

#### 2. **Disjoint Sets 解的是等價類問題，不是排序問題**

Disjoint Set 通常用來處理：

* 連通元件分析（如圖論中的 union-find）
* 群體歸類（equivalence class）
* Kruskal's MST 演算法中用來判斷是否會形成圈

而排序要的是：

> 將所有元素依據大小**排列順序**

Disjoint Set 無法得知元素間的**全序（total order）**，只知道「是否屬於同一集合」。

## Graph

### **基本定義**

* **圖 (Graph)**：$G = (V, E)$，由「頂點集合」$V$ 和「邊集合」$E$ 組成。
* **鄰接串列（Adjacency List）**：適合稀疏圖（邊遠小於 $V^2$），空間為 $\Theta(V + E)$。
* **鄰接矩陣（Adjacency Matrix）**：適合稠密圖（邊接近 $V^2$），空間為 $\Theta(V^2)$。

### **22.2 廣度優先搜尋 (BFS, Breadth-First Search)**

從起點 $s$ 找出每個頂點的「最短路徑長度」（以邊數計）。
$O(V + E)$，每個節點與邊最多處理一次。
```plaintext
1. 初始化所有節點為 WHITE、距離為 ∞、前驅為 NIL
2. 將起點設為 GRAY，距離為 0，加入佇列 Q
3. 當 Q 不為空：
    - 將 u 出佇列
    - 掃描所有 u 的鄰居 v
        - 若 v 為 WHITE：
            - 標記為 GRAY
            - 設定距離 d[v] = d[u] + 1
            - 前驅 π[v] = u
            - 將 v 加入 Q
    - u 標記為 BLACK
```

```
BFS(G, s)

1.  for each vertex u ∈ V(G) – {s} 
2.      color[u] ← WHITE         // 未探索
3.      d[u] ← ∞                 // 與起點的距離初始化為無限大
4.      π[u] ← NIL               // 前驅節點初始化為 NIL

5.  color[s] ← GRAY              // 起點發現中
6.  d[s] ← 0
7.  π[s] ← NIL
8.  Q ← {s}                      // 初始化佇列 Q

9.  while Q ≠ ∅
10.     u ← DEQUEUE(Q)
11.     for each v ∈ Adj[u]
12.         if color[v] = WHITE
13.             color[v] ← GRAY
14.             d[v] ← d[u] + 1
15.             π[v] ← u
16.             ENQUEUE(Q, v)
17.     color[u] ← BLACK         // u 探索完成
```

### BFS Finds Shortest Paths：證明流程

#### **Lemma 1. 每條邊(u, v) 都符合：**

$$
\delta(s, v) \leq \delta(s, u) + 1
$$

即：若存在邊 $(u, v)$，則從起點 `s` 到 `v` 的最短距離不會超過 `u` 的最短距離加 1（因為可以從 `u` 走一步到 `v`）。

#### **Lemma 2. BFS 記錄的 d\[v] ≥ δ(s, v)**

> （δ 為從 `s` 到 `v` 的實際最短距離）

**證明（歸納法）**：

* 初始時只有起點 `s`，`d[s] = 0 = δ(s, s)`
* 假設 BFS 在前 $k$ 步皆正確地設定 $d[u] ≥ \delta(s, u)$
* 第 $k+1$ 步中，從某個節點 $u$ 探索鄰居 $v$，若 $v$ 是第一次被訪問，則設：

  $$
  d[v] = d[u] + 1 \geq \delta(s, u) + 1 \geq \delta(s, v)
  $$
* 所以 $d[v] \geq \delta(s, v)$ 成立。

#### **Lemma 3. BFS 中的佇列順序會遵守 d 值單調不減**

* BFS 使用 FIFO 佇列
* 若 $v_i$ 較早進入佇列，則其距離 $d[v_i] \leq d[v_j]$
* 所以 BFS 探索是按**層級（距離）擴展**，這對保證最短路徑非常關鍵

#### **Theorem: BFS 找到的 d\[v] = δ(s, v)**

> **BFS 對於每個從 `s` 可達的頂點 `v`，最終記錄的 `d[v]` 一定等於從 `s` 到 `v` 的最短邊數。**

**證明結論：**

* 從 Lemma 2 知：BFS 不會低估距離
* 從 BFS 流程知：一旦有機會從距離為 δ(s, v) 的節點訪問到 `v`，BFS 就會以最短距離訪問 `v`（因為佇列順序保證這是第一次訪問）
* 所以實際上 BFS 訪問到 `v` 時，`d[v] = δ(s, v)`

---

### Theorem 22.5: Correctness of BFS

#### (1) BFS will discover all reachable vertices

* BFS 使用佇列從 $s$ 開始探索，對每個已探索到的節點 $u$，會檢查 $\text{Adj}[u]$。
* 若 $v \in \text{Adj}[u]$ 尚未探索，則加入佇列。
* 因為 BFS 會將所有鄰接節點納入佇列，所以**所有從 $s$ 可達的節點一定會被訪問到**。

---

#### (2) BFS computes the shortest-path distance

* BFS 是按層（distance）探索，第一次發現 $v$ 時，$d[v] = d[u] + 1$，其中 $u$ 是到目前為止最短的節點。
* 根據之前的 Lemma（參見你之前問的 Proof of Shortest Path），我們有：

  $$
  d[v] \geq \delta(s, v) \quad 且 \quad d[v] \leq \delta(s, v)
  $$
* 所以：

  $$
  \boxed{d[v] = \delta(s, v)}
  $$

---

#### (3) BFS gives a shortest path tree

* 對於每個可達的 $v \ne s$，其前驅節點 $\pi[v]$ 是第一次發現 $v$ 時的節點 $u$
* 因此我們可以沿著 `π[v] → π[π[v]] → ... → s` 的方向反推出一條從 $s$ 到 $v$ 的最短路徑。
* 這條路徑的長度即為 $d[v] = \delta(s, v)$

---

### **22.3 深度優先搜尋 (DFS, Depth-First Search)**
探索圖的結構、分類邊的類型、生成 DFS 樹。


```
DFS(G)
1.  for each vertex u ∈ V[G]
2.      color[u] ← WHITE            // 初始化為未探索
3.      π[u] ← NIL                 // 前驅節點設為 NIL
4.  time ← 0                       // 全域時間變數初始化
5.  for each vertex u ∈ V[G]
6.      if color[u] = WHITE
7.          then DFS-VISIT(u)

-----------------------------------------

DFS-VISIT(u)
1.  color[u] ← GRAY                 // 探索中
2.  time ← time + 1
3.  d[u] ← time                    // 紀錄發現時間
4.  for each v ∈ Adj[u]           // 掃描鄰居
5.      if color[v] = WHITE       // 若尚未探索
6.          then π[v] ← u
7.               DFS-VISIT(v)
8.  color[u] ← BLACK               // 結束探索
9.  time ← time + 1
10. f[u] ← time                   // 紀錄完成時間
```

---

### **Parenthesis Theorem（括號定理）**

對於任何兩個節點 $u, v$，其時間區間 $[d[u], f[u]]$ 和 $[d[v], f[v]]$ 有下列三種關係之一：

1. **不相交**：代表兩者在不同 DFS 樹中
2. **一個完全包含另一個**：
   * 若 $[d[u], f[u]] \subset [d[v], f[v]]$，則 $u$ 是 $v$ 的子孫
   * 若 $[d[v], f[v]] \subset [d[u], f[u]]$，則 $v$ 是 $u$ 的子孫

---

### **White Path Theorem**

在 DFS 過程中，**若存在一條從 $u$ 到 $v$ 的全白色節點路徑，則 $v$ 是 $u$ 的後代。**

---

### **邊的分類（Edge Classification）**

DFS 中的邊 $(u, v)$ 可根據 `d[]` 和 `f[]` 的關係分成以下幾類：

| 類型           | 定義                         | 意義                |
| ------------ | -------------------------- | ----------------- |
| Tree edge    | $v$ 是 DFS 首次發現的節點          | DFS tree 的一部分     |
| Back edge    | $v$ 是 $u$ 的祖先              | 存在 **環**（重要於循環偵測） |
| Forward edge | $v$ 是 $u$ 的子孫，但不是首次發現      | 非 tree edge 的後代訪問 |
| Cross edge   | $u$ 和 $v$ 屬於不同 DFS 樹或已完成節點 | 跨越不同分支的邊          |

判斷方式依據：時間戳記關係，如 $d[u] < d[v] < f[v] < f[u]$ 為 forward edge

## **拓撲排序 (Topological Sort)**

> $\Theta(V + E)$ 

對於有向無環圖（DAG），將頂點排序，使得對每個邊 $(u, v)$，$u$ 必在 $v$ 前。

1. DFS 並紀錄每個頂點完成時間 $f[u]$
2. 依照 $f[u]$ 由大至小排序

## 強連通元件（Strongly Connected Components, SCC）

> $O(V + E)$，其中 $V$ 為頂點數，$E$ 為邊數。

在有向圖（Directed Graph）中，如果從某個節點 $u$ 出發可以到達 $v$，同時從 $v$ 也可以到達 $u$，那麼這兩個節點屬於同一個「強連通元件」。

---

### 演算法步驟（STRONGLY-CONNECTED-COMPONENT(G)）

1. **第一次 DFS：**
   * 對圖 $G$ 執行 DFS，記錄每個節點的完成時間 $f[u]$。
2. **反向圖（$G^T$）：**
   * 建立轉置圖 $G^T$，將所有邊的方向反轉。
3. **第二次 DFS：**
   * 在 $G^T$ 上根據第一次 DFS 的 $f[u]$ 降序進行 DFS。
   * 每棵 DFS 樹對應一個強連通元件。
4. **輸出結果：**
   * 每棵 DFS 樹的所有節點就是一個 SCC。

### SCC 演算法正確性的三大關鍵步驟

#### 1. **DFS 的完成時間排序會正確地引導 SCC 分離**

* **Lemma 22.14（引理）：**
  若 $C$ 和 $C'$ 是圖 $G$ 中不同的強連通元件，且存在一條邊 $(u, v) \in E$，其中 $u \in C$、$v \in C'$，
  則在對 **原圖 $G$** 執行 DFS 時，**$f(C) > f(C')$**。
  👉 這表示：若有一條邊從 $C$ 指向 $C'$，那麼 DFS 將會**晚一點**完成 $C$。

---

#### 2. **對 $G^T$ 做 DFS，並依照完成時間遞減順序遍歷，可以正確分離 SCC**

* **關鍵觀察：**

  * $G$ 中的邊 $u \to v$ 會變成 $v \to u$（在 $G^T$ 中）。
  * 若 $f(C) > f(C')$，則在 $G^T$ 中不會有邊從 $C'$ 回到 $C$。
  * 所以在 DFS 的主循環中，照 $f[u]$ 降序進行時，會先完全遍歷 $C$，再進入其他 SCC，不會交錯。

---

#### 3. **結論與定理（Theorem 22.16）：**

> **STRONGLY-CONNECTED-COMPONENTS(G)** 演算法可以正確找出所有強連通元件。

* 因為：

  1. DFS 確保了 finishing time $f[u]$ 的順序性；
  2. $G^T$ 反轉所有邊，使得成分間的方向也反轉；
  3. 根據 DFS 的探索順序與 $f[u]$ 降序的特性，會從「沒有出邊的 SCC」開始，層層分離不會混淆。

---

### 為什麼 DFS 順序重要？

* 若照隨機順序做 DFS，可能在第二次 DFS 探索時會跨越多個 SCC，無法正確區分它們。
* 而照 $f[u]$ 降序訪問，保證每次 DFS 探索都限制在同一個 SCC。

## Minimum Spanning Tree（MST）最小生成樹

* **Minimum Spanning Tree（最小生成樹）** 是一棵涵蓋所有頂點的無向子圖樹，且邊的總權重最小。
* 給定一張**連通的加權無向圖** $G = (V, E)$，其 **MST** 是一個邊的子集 $A \subseteq E$，使得 $A$ 是樹，並且總權重最小。
* MST 有 $|V| - 1$ 條邊
* MST 不包含 cycles
* MST 可能不為 unique，但 total weights 會相同
* 可以有不同邊組成的 MST 嗎？ **可以**，若邊權重有相同數值，可能會產生多個 MST，但它們的**總權重相同**。

--- 

### 建構 MST：`GENERIC-MST(G, w)`

```plaintext
1  A ← ∅
2  while A 不形成一棵生成樹 do
3      找一條對 A 是「安全（safe）」的邊 (u, v)
4      A ← A ∪ {(u, v)}
5  return A
```

### Safe Edge（安全邊）

* 安全邊的意義：若 $A$ 是某個 MST 的子集，則邊 (u, v) 是安全的當且僅當 $A ∪ \{(u, v)\}$ 也是某個 MST 的子集。

---

### 切割 (Cut)

* 將 $V$ 分為兩個不重疊的集合 $S$ 與 $V - S$，稱為一個切割。
* 邊 (u, v) **跨越**這個切割，若一端在 $S$，一端在 $V - S$。

### 輕邊 (Light Edge)

* 在所有跨越一個切割的邊中，**權重最小的邊**稱為輕邊。
* 若該切割「尊重（respect）」目前的邊集 $A$（即 $A$ 中的邊都不跨越切割），則這條輕邊為安全邊。

### 📐 安全邊定理（Theorem 23.1）

* 若一個輕邊跨越一個尊重 $A$ 的切割，則它是安全邊。

## Kruskal’s Algorithm

[詳細版本](https://mycollegenotebook.medium.com/kruskal-algorithm-deb0d64ce271)

```plaintext
1  A ← ∅
2  對每個頂點 v 呼叫 MAKE-SET(v)
3  將所有邊按權重遞增排序
4  依序檢查每條邊 (u, v)：
5      若 FIND-SET(u) ≠ FIND-SET(v)
6          A ← A ∪ {(u, v)}
7          UNION(u, v)
8  return A
```

* 以邊為中心，從小權重邊開始，避免形成環。
* 使用 **Disjoint Set（不交集合）資料結構** 來檢查連通性。

## Prim’s Algorithm

[Prim’s Algorithm](https://mycollegenotebook.medium.com/prims-algorithm-47b7686de488)

> 使用 heap：$O(E + V \log V)$

```plaintext
MST-PRIM(G, w, r)
1.  Q ← V[G]                             // 初始化優先佇列 Q（所有節點）
2.  for each u ∈ Q
3.      key[u] ← ∞                       // 預設距離無限大
4.      π[u] ← NIL                       // 父節點初始化為 NIL
5.  key[r] ← 0                           // O(logN), 起始點權重設為 0

6.  while Q ≠ ∅                          // O(VlogN), 還有節點未加入 MST
7.      u ← EXTRACT-MIN(Q)              // 選出 key 最小的節點
8.      for each v ∈ Adj[u]             // 掃描所有相鄰節點
9.          if v ∈ Q and w(u, v) < key[v]
10.             π[v] ← u                // 更新 v 的父節點為 u
11.             key[v] ← w(u, v)        // 更新最小邊權重

```

* 以**點為中心**逐步擴張。
* 每次加入與目前生成樹最靠近的點。

### MST 是否可以有「不同邊集合但總權重相同」的情況？

> Ans: 看情況
* 在權重唯一的情況下，MST 具有**唯一性** -> **No**
* 若權重可能重複，可能會有兩種以上的 MST 存在 -> **Yes**

## Maximum Flow（最大流問題）

### Flow Network（流量網路）

* 一個有向圖 $G = (V, E)$，其中每條邊 $(u, v)$ 都有一個非負的容量 $c(u, v)$。
    * 如果 $(u, v)$ 存在，則不存在 $(v, u)$ (單向)
    * 如果 edge $(u, v)$ 不存在，$c(u, v) = 0$
    * 不允許 self-loop
* 包含兩個特殊節點：
    * **Source**（源點）$s$：物品或資訊的起始點。
    * **Sink**（匯點）$t$：物品或資訊的終點。

---

### Maximum-Flow Problem（最大流問題）


找出從 $s$ 到 $t$ 的最大可能流量（flow），同時滿足以下條件：
  1. **容量限制（Capacity Constraint）**：對任意邊 $(u, v)$，有 $0 \le f(u, v) \le c(u, v)$。
  2. **流量守恆（Flow Conservation）**：對任意中繼節點 $v \ne s, t$，進入的總流量等於流出的總流量。

---

### Ford-Fulkerson Method（福特-福克森方法）


[Ford-Fulkerson Method 講解](https://www.youtube.com/watch?v=8sLON0DqLZo)

> 這不是單一演算法，而是一系列方法的總稱。核心概念為「不斷找增廣路徑」。

* **流網路**（Flow Network）
  有向圖 $G=(V,E)$，每條邊 $(u,v)$ 有非負容量 $c(u,v)$。指定源點 $s$、匯點 $t$。

* **殘量網路**（Residual Network）
  對於當前流 $f$，定義殘量容量：
  $$
    c_f(u,v) = c(u,v) - f(u,v)\quad\text{(正向)};\quad
    c_f(v,u) = f(u,v)\quad\text{(反向)}.
  $$
  殘量邊表示可以增加（或回退）的流量。

#### 演算法步驟

1. **初始化流**
   對所有 $(u,v)\in E$，設 $f(u,v)=0$。
2. **尋找增廣路徑**（Augmenting Path）
   在殘量網路 $G_f$ 中，用 DFS 或 BFS 找到一條從 $s$ 到 $t$ 的路徑 $P$，使得每條邊的殘量 $c_f>0$。
3. **更新流**
   * 計算路徑瓶頸容量（bottleneck capacity）：
     $\displaystyle b = \min_{(u,v)\in P} c_f(u,v)$。
   * 對路徑上的每條邊 $(u,v)$：
     $$
       f(u,v) \leftarrow f(u,v) + b,\quad
       f(v,u) \leftarrow f(v,u) - b.
     $$
4. **重複**
   重複步驟 2\~3，直到找不到增廣路徑為止。

演算法結束時，$f$ 即為最大流，且根據最大流–最小割定理，其值等於某一最小割的容量。

#### 正確性保證

* 每次沿增廣路徑加流後，流量仍滿足容量限制與流量守恆。
* 若無增廣路徑，則無法再增加流量，當前流即為最大流。

#### 時間複雜度

* 若用 **DFS** 任意找增廣路徑，複雜度為 $O(E\cdot |f^*|)$，其中 $|f^*|$ 是最大流值（可能很大）。
* 用 **Edmonds–Karp**（每次用 **BFS** 找最短增廣路徑）可保證 $O(VE^2)$。
* 進階如 **Dinic** 可達 $O(V^2E)$ 或更優。

#### 注意事項

* **整數容量**（Integer capacities）下 Ford–Fulkerson 保證收斂；若容量為實數，理論上可能無限迭代。
* 增廣路徑的選取策略會影響效率，但不影響正確性（只要每次找到的路徑容量均為正）。

### Max-Flow Min-Cut Theorem

1. **流網路**（Flow Network）

   * 有向圖 $G=(V,E)$，每條邊 $(u,v)$ 有非負容量 $c(u,v)$。
   * 指定源點 $s$（source）與匯點 $t$（sink），且圖中不存在從 $t$ 到 $s$ 的路徑。

2. **可行流**（Feasible Flow）

   * 流量函數 $f:V\times V\to\mathbb{R}$，滿足：

     1. **容量限制**（Capacity Constraint）

        $$
          0 \le f(u,v) \le c(u,v)\quad\forall(u,v)\in E
        $$
     2. **流量守恆**（Flow Conservation）
        對所有中介節點 $u\ne s,t$：

        $$
          \sum_{v} f(v,u) = \sum_{v} f(u,v)
        $$
   * **流量值**（Value of Flow）定義為從源點流出的總量：
     $\displaystyle |f| = \sum_{v} f(s,v)$。
     
3. **割**（Cut）
   * 將頂點集合 $V$ 切分為 $(S,T)$，其中 $s\in S$、$t\in T$。
   * **割的容量**（Capacity of Cut）
     $$
       c(S,T) = \sum_{u\in S,\,v\in T} c(u,v)
     $$

---

#### 定理敘述

> **最大流–最小割定理**
> 在任一流網路中，對所有可行流 $f$ 與所有 $s\!-\!t$ 割 $(S,T)$，必有
>
> $$
>   |f| \le c(S,T).
> $$
>
> 且存在某一可行流 $f^*$ 和某一割 $(S^*,T^*)$，使得
>
> $$
>   \max_f |f| \;=\;\min_{(S,T)} c(S,T).
> $$

* **直觀意義**：流量再怎麼增加，都受任一割的瓶頸（割邊總容量）限制；定理保證：只要找到最大流，就同時找到了「最小瓶頸割」。

---

#### 證明大綱

1. **弱對偶性**（Weak Duality）
   * 任一可行流 $f$ 和任一割 $(S,T)$，都有 $|f|\le c(S,T)$。
   * 證法：把流量拆成跨越 $S\to T$ 的貢獻，加上 $T\to S$ 的扣除，配合守恆可得不超過割容量。
2. **強對偶性**（Strong Duality） via Ford–Fulkerson
   * 使用 Ford–Fulkerson 演算法（或 Edmonds–Karp）不斷在殘量網路（residual network）中尋找增廣路徑（augmenting path），直到無增廣路徑為止。
   * 當無法再增廣時，將所有從 $s$ 可達的節點標記為 $S^*$，其餘為 $T^*$，即可證明 $|f^*|=c(S^*,T^*)$。

---

#### 演算法意涵

* **找到最大流** ⇔ **找到最小割**：透過構造殘量網路中的可達集，自動對應一個最小割。
* **時間複雜度**：
  * Ford–Fulkerson 需 $O(E\cdot \text{max\_flow})$
  * Edmonds–Karp 保證 $O(VE^2)$
  * Dinic’s Algorithm 則可達 $O(V^2E)$ 或 $O(\sqrt V\,E)$（unit networks）

---

### 補充：限制與注意

* **不允許反向邊**：需將「正向容量」與「反向可回退容量」分別建模於剩餘網路。
* **多源點或多匯點問題**：可透過加上超源點（super source）或超匯點（super sink）來解決。