資料結構：圖形
圖形（Graph）是資料結構中極為重要的非線性結構，用於描述物件與物件間的關聯性。無論是社群網路、人際關係、地圖導航，還是網頁連結，這些都可以以圖形結構來表示與處理。
一、圖形的定義
圖形是一組節點（Vertex，也稱為頂點）及邊（Edge）的集合，用以描述節點之間的關聯。圖形可表示為 $G = (V, E)$，其中：
- $V$：頂點的集合。
- $E$：邊的集合，每條邊連接兩個頂點。
二、圖形的分類
1. 無向圖（Undirected Graph）
若邊沒有方向，即 $(u, v)$ 與 $(v, u)$ 表示相同的邊，則稱為無向圖。
2. 有向圖（Directed Graph）
若邊具備方向，即 $(u, v)$ 表示從 $u$ 到 $v$ 的邊，則稱為有向圖。
3. 帶權圖（Weighted Graph）
若邊帶有數值權重，代表兩個節點之間的成本、距離或時間，則稱為帶權圖。
4. 簡單圖（Simple Graph）
圖中沒有重複邊，且沒有自環（節點到自己的邊）。
5. 完全圖（Complete Graph）
圖中任意兩個不同節點均存在邊。
6. 稀疏圖與稠密圖
- 稀疏圖：邊數遠小於節點數的平方。
- 稠密圖：邊數接近節點數的平方。
三、圖的基本術語
| 術語 | 說明 |
|---|---|
| 節點度數 | 與該節點相連的邊數。在有向圖中，包含入度（In-degree）與出度（Out-degree）。 |
| 鄰接節點 | 與某節點有邊相連的其他節點。 |
| 路徑 | 一系列相連的邊和節點序列。 |
| 環路 | 起點和終點相同的路徑。 |
| 連通圖 | 任意兩節點間存在路徑的無向圖。 |
| 強連通圖 | 有向圖中任意兩節點都有路徑互達。 |
四、圖的存儲方式
1. 鄰接矩陣（Adjacency Matrix）
用 $n \times n$ 的二維陣列表示，若節點 $u$ 與 $v$ 有邊，則矩陣 $A[u][v] = 1$（或權重），否則為 0。
- 空間複雜度：$O(V^2)$
- 查找邊的時間複雜度：$O(1)$
2. 鄰接表（Adjacency List）
每個節點對應一個鄰接節點的串列。
- 空間複雜度：$O(V + E)$
- 查找邊的時間複雜度：$O( ext{度數})$
五、圖的基本操作
1. 建立圖
初始化節點與邊的集合。
2. 新增/刪除節點
更新節點集合，同時調整相關邊。
3. 新增/刪除邊
更新邊的集合或鄰接表、鄰接矩陣。
4. 查詢鄰接節點
遍歷節點的鄰接表或查閱鄰接矩陣。
六、圖的遍歷演算法
1. 深度優先搜尋（DFS）
沿著一條路徑深入探索，直至無法前進，再回溯。
void DFS(int v) {
visited[v] = true;
for (int u : adj[v]) {
if (!visited[u]) {
DFS(u);
}
}
}2. 廣度優先搜尋（BFS）
由起點開始，逐層向外擴展。
void BFS(int start) {
queue<int> q;
q.push(start);
visited[start] = true;
while (!q.empty()) {
int v = q.front(); q.pop();
for (int u : adj[v]) {
if (!visited[u]) {
visited[u] = true;
q.push(u);
}
}
}
}七、圖的常用演算法
1. 最短路徑
- Dijkstra 演算法：適用於非負權重圖。
- Bellman-Ford 演算法：允許負權重，適用於含負權邊圖。
2. 最小生成樹（MST）
- Prim 演算法：貪婪策略選擇邊構建最小生成樹。
- Kruskal 演算法：按邊權排序，逐步連接樹。
3. 拓撲排序
適用於有向無環圖（DAG），給出節點的線性順序，保證所有邊方向一致。
八、圖的時間與空間複雜度
| 操作 | 鄰接矩陣 | 鄰接表 |
| 查找邊 | O(1) | O(度數) |
| 插入邊 | O(1) | O(1) |
| 遍歷所有邊 | O(V^2) | O(V + E) |
九、圖的應用場景
- 地圖導航：最短路徑搜尋。
- 社群網路分析：好友推薦、影響力分析。
- 網頁排名：PageRank 演算法。
- 電路設計：拓撲排序。
- 資料流分析：圖遍歷。
十、圖的優缺點
優點
- 適用於關係型資料建模。
- 適合解決路徑、網路等問題。
缺點
- 鄰接矩陣佔用大量空間。
- 操作與演算法複雜度較高。
十一、結論
圖形是描述複雜關聯關係的理想工具，掌握圖的基本概念、存儲方式與常見演算法，不僅有助於解決實際問題，更能提高程式設計能力與演算法思維。