# 演算法 - 鮑興國
> 維護者：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\}
$$
若輸入矩陣維度為：
```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]` 的最小值。
### 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
```
### 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)
```
#### 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)
```
這樣能夠將所有連通的節點合併在同一個集合裡，完成連通元件的分析。
---
### 三、資料結構實作
#### 1. Linked List 實作
* 每個集合用一個 linked list 表示。
* 儲存 head/tail 方便合併。
* UNION 的效率為 $O(n)$，因為要更新整個鏈結串列中的 pointer。
* 每個節點儲存：
* 自身值 `x`
* 指向集合代表元素的指標 `x.rep`
* 每個集合儲存：
* 頭尾指標 `head`、`tail`
* 節點數量（可選）
##### 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）來解決。
Sign in with Wallet
Connect another wallet