# 基本圖論

## 圖論名詞介紹

### 圖 (Graph) / 節點 (Vertex) / 邊 (Edge)
- 圖（`Graph`）：一種由「節點（頂點，`Vertex`, `plural: Vertices`）」與「邊(`Edge`)」組成的結構，用以描述「關係」或「連結」。
- 記號：常寫作 \( G = (V, E) \)，其中
- \( V \)：節點集合
- \( E \)：邊集合（每一條邊連結 1 或 2 個節點，依有向／無向而定）
- 節點（`Vertex`）：圖的基本單位，可以代表人、城市、伺服器、檔案、網頁等。
- 邊（`Edge`）：連結節點與節點之間的關係或互動，可以代表道路、好友關係、流量、依賴性等。


#### 生活中的例子 - 圖
- 社群網路：節點＝使用者，邊＝互為好友（無向）或「追蹤」（有向）。
- 道路地圖：節點＝路口，邊＝道路（可帶距離或時間作為邊權）。
- 檔案依賴：節點＝模組，邊＝依賴關係（常為有向）。
- 網頁連結：節點＝網頁，邊＝超連結（有向）。
- 電路連線、組織架構、流程節點等也可建模為圖。


---

### 有向圖 / 無向圖
- 無向圖（`Undirected Graph`）：邊 (u, v) 無方向，表示「對稱關係」。好友、雙向管線、無向連線等。
- 有向圖（`Directed Graph / Digraph`）：邊 <u, v> 有方向，表示「由 u 指向 v」。關注、單向管制、資料流、依賴順序等。
- 混合圖：同時存在有向與無向邊（可以先不要理他，暫時遇不到）。
- 自迴圈（`Self Loop`）：由節點指向自身的邊（u, u）。
- 重邊（`Multi-Edge`）：兩節點間有多條邊（可能代表多種不同型態的連結），簡單圖（Simple Graph）中不允許重邊與自迴圈。

#### 生活中的例子 - 有向圖（？）
- `Instagram`：A 追蹤 B 不代表 B 一定追蹤 A → 有向。
- 物流流向：倉庫 A 發貨到門市 B。
- 任務依賴：任務 A 必須在任務 B 前完成（A → B）。

---

### 圖上的資訊
- 結構資訊：哪兩個節點相連。
- 額外屬性：
- 邊權（`Edge Weight`）
- 點權（`Node / Vertex Weight`）
- 標籤（`Label`）、容量（`Capacity`）、流量（`Flow`）、顏色（`Color`）等
- 在資料結構實作上，通常使用額外陣列或結構體儲存。
- 

---

### 度數 (無向圖)
- 節點`u`的度（`Degree`）：與 u 相接的邊數量。
- 葉節點（`Leaf`）：度 = 1 的節點（在樹結構中尤為常見）。
- 性質：無向圖中所有節點度數總和 = 2 × 邊數。

### 度數 (有向圖)
- 入度（`In-Degree`）：指向該節點的邊數。
- 出度（`Out-Degree`）：由該節點指向外部的邊數。
- 有向圖全部節點入度總和 = 邊數，全部節點出度總和 = 邊數。

---

### 邊權 (無向圖)
- 無向邊 (u, v) 之權重 w(u, v) 表示「距離 / 成本 / 時間 / 容量」等。
- 假設對稱則 w(u, v) = w(v, u)。

#### 生活中的例子 - 邊權
- 道路距離、通話費率、網路帶寬、時間成本。
- 可同時存在多種權（如距離與花費），可用多欄位儲存。

### 邊權 (有向圖)
- 有向邊 <u, v> 的權重 w(u, v) 可與 w(v, u) 不同（若反向邊存在）。
- 「雙向的邊可能有不同邊權」：例如上坡耗時 10，下坡耗時 3。


---

### 點權
- 每個節點本身也可附加權重或屬性：例如人口數、儲存容量、風險值。
- 可能用於後續計算（例如：選擇最優節點、累加點權）。

#### 生活中的例子 - 點權
- 城市節點：人口 / GDP / 需求量。
- 伺服器節點：CPU 核心數 / 記憶體大小。
- 社群使用者：粉絲數。

---

### 路徑
- 路徑：不重複節點的連續邊序列。
- 長度：可用「邊數」或「邊權總和」定義。
- 例：在無向圖 1–2–3–4 中，1→4 的路徑為 (1,2,3,4)。

---

### 路徑有關名詞
- `Walk`（步行）：節點與邊序列，允許重複節點或邊。
- `Trail`（蹤徑）：不重複邊，但允許節點重複。
- `Path`（路徑）：不重複節點（因此亦不重複邊），又稱「簡單路徑」。
- `Cycle`（環）：起點與終點相同且長度 ≥ 1（有向圖中自迴圈視為長度 1 環，無向圖通常要求邊數 ≥ 3 且不重複節點除起終點）。


---

### 環 (有向圖)
- 有向環（`Directed Cycle`）：一串節點 v1 → v2 → … → vk → v1 且 k ≥ 1（k=1 為自迴圈）。
- 允許方向性閉合。
- 例：A→B→C→A。


### 環 (無向圖)
- 無向環：一序列節點 v1 - v2 - … - vk - v1，k ≥ 3，且除起終點外不重複節點。
- 例：1—2—3—1。
- 在無向樹中不存在任何環。


---

### 建立一張圖
1. 明確節點語意（人 / 地點 / 任務 / 物件）。
2. 明確邊語意（互動 / 通路 / 順序 / 資料流）。
3. 決定有向或無向（方向是否重要）。
4. 是否需要邊權 / 點權（量化指標？）。
5. 是否允許多重邊或自迴圈（若不是必要，建議避免）。
6. 選擇儲存方式，依圖大小與操作需求選擇。

---

### 生活中的例子
| 主題 | 例子 | 類型 |
|------|------|------|
| 無向圖 | Facebook 好友 | 不區分方向 |
| 有向圖 | Twitter 追蹤、物流運輸、課程先後修 | 有方向 |
| 邊權 | 道路距離、傳輸延遲、費用 | (u,v,w) |
| 不同方向不同權 | 上坡/下坡耗時、匯率（A→B 與 B→A 差異） | 有向加權 |
| 點權 | 城市人口、伺服器資源、節點重要性 | value[v] |

---

## 總結
圖是一個挺抽象的東西，第一次學會吸收很多專有名詞一時搞不太懂是正常的，基本上就慢慢練習，同時如果疑惑圖到底能幹嘛，等等的課會上圖有關的演算法

---