Learning Objectives
- 分辨有向圖、無向圖與加權圖，算出節點的入度與出度
- 用邊列表、鄰接矩陣、鄰接串列存同一張圖，說出每一種在記憶體裡存了什麼
- 比較三種表示法的空間（O(E)、O(V²)、O(V + E)）與查一條邊、列出鄰居、算入度的成本
- 依圖是稠密還是稀疏、程式最常做哪一種操作，選擇表示法
- 把一種表示法轉換成另一種，處理無向邊在矩陣與串列裡出現兩次的問題
同一張圖，三種存法
捷運路線、社群網站的追蹤關係、課程的先修關係、網頁之間的連結，都可以畫成圖（graph）： 一群節點（node，也叫頂點 vertex）加上連接它們的邊（edge）。
畫在紙上的圖一眼就看得懂，程式卻只能把它存成陣列、串列這些結構。常見的存法有三種：
| 表示法 | 存什麼 |
|---|---|
| 邊列表（edge list） | 一筆一筆列出每條邊：「從哪裡到哪裡、權重多少」 |
| 鄰接矩陣（adjacency matrix） | V × V 的表格，第 u 列第 v 行記錄 u 到 v 有沒有邊 |
| 鄰接串列（adjacency list） | 每個節點一個串列，列出它連到哪些節點 |
三種存的是同一張圖，差別在佔多少記憶體、哪些操作快、哪些操作慢。這一課把三種都做出來，量一量各自的成本。
這一課只談「怎麼存」。在圖上走訪的演算法（廣度優先搜尋 BFS、深度優先搜尋 DFS）請看演算法軌第 16、17 課， 那兩課用的就是這裡的鄰接串列。
有向、無向、加權
先把幾個名詞說清楚。V 是節點數、E 是邊數，節點編號用 0 到 V - 1。
- 無向圖（undirected graph）：邊沒有方向，u — v 表示兩人互相是朋友。度數（degree）是連著幾條邊。
- 有向圖（directed graph）：邊有方向，u → v 表示 u 追蹤 v，不代表 v 追蹤 u。 從 u 出去的邊數叫出度（out-degree），進入 v 的邊數叫入度（in-degree）。
- 加權圖（weighted graph）：每條邊帶一個數字，例如距離、時間、票價。
邊數有上限。不算自己連到自己的邊（自環）時：
| 最多幾條邊 | |
|---|---|
| 無向圖 | V(V - 1) / 2（每兩個節點最多一條） |
| 有向圖 | V(V - 1)（每兩個節點兩個方向各一條） |
E 接近這個上限的圖叫稠密圖（dense graph），E 遠小於上限（例如 E 和 V 差不多大）的叫稀疏圖（sparse graph）。 後面選表示法時，這個區別最重要。
接下來三個範例都用同一張有向加權圖：5 個節點、6 條邊，例如 0 → 1 的權重是 4。
邊列表：一筆一筆列出邊
邊列表就是一個 E × 3 的表格，每一列是一條邊 [u, v, w]。算出度與入度時，每一筆邊讓起點的出度、終點的入度各加 1。後半段查「2 → 3 有沒有邊」：邊列表沒有任何索引，只能從第 0 筆往下找；查不存在的 3 → 2 時，6 筆全部看完才能確定。
邊列表適合做什麼
邊列表的空間是 O(E)：有幾條邊就存幾筆，沒有任何浪費。它也是最自然的輸入格式， 很多資料檔就是一行一條邊（例如 CSV 的「起點,終點,權重」）。
但它沒有依節點整理，所以任何「和某個節點有關」的問題都要掃過全部 E 筆：
| 操作 | 邊列表 |
|---|---|
| u → v 有沒有邊 | O(E) |
| 列出 u 的鄰居 | O(E) |
| 算 v 的入度或出度 | O(E) |
| 加一條邊 | O(1)（接到尾端） |
適合邊列表的場合：只需要「把所有邊看過一遍」的演算法。例如把邊依權重排序、一條一條決定要不要選的 Kruskal 最小生成樹（演算法軌第 19 課）。 需要常常問「u 連到誰」時，就該換成下面兩種。
鄰接矩陣：V × V 的表格
有向圖的每條邊只填一格：m[u][v] 放 u → v 的權重，所以矩陣不對稱，m[2][3] 是 8、m[3][2] 是 0。查一條邊只要看一格；但列出 2 的鄰居要把第 2 列（橫的）5 格全部看完，算 1 的入度要把第 1 行（直的）5 格看完，不管 2 實際上有幾個鄰居。
鄰接矩陣在記憶體裡
鄰接矩陣是一個二維陣列，C++ 的 int m[V][V] 或 Java 的 new int[V][V] 依列優先一列接一列存放（第 02 課的位址公式）。
不管有幾條邊，都要 V × V 格，空間 O(V²)。
| 操作 | 鄰接矩陣 |
|---|---|
| u → v 有沒有邊 | O(1)，看 m[u][v] 一格 |
| 列出 u 的鄰居 | O(V)，看第 u 列整列 |
| 算 v 的入度 | O(V)，看第 v 行整行 |
| 加邊、刪邊 | O(1) |
幾個實作細節：
- 無向圖的矩陣左右對稱，加一條邊要改
m[u][v]和m[v][u]兩格。只存一半（上三角）可以省下將近一半空間， 但每次讀取都要先比較 u、v 的大小，程式比較囉唆。 - 權重 0 的問題：範例用 0 表示「沒有邊」，前提是權重不會是 0。權重可能是 0 或負數時， 沒有邊要改用一個不可能出現的值（例如很大的數當作無限大），或另外存一個布林矩陣。
- 不需要權重時可以一格一個位元：用位元陣列（bitset）存，V = 10,000 時是 10⁸ 個位元，約 12.5 MB；
用
int存要 400 MB。
鄰接串列：每個節點一個串列
adj[u] 只存從 u 出去的邊，每一筆是 [終點, 權重]。列出 2 的鄰居只要走過 adj[2] 的 2 筆，和節點總數無關。代價在入度：鄰接串列只記「從哪裡出去」，要知道「誰指向我」只能把每個串列都掃一遍。
鄰接串列在記憶體裡
鄰接串列是「V 個串列」：一個長度 V 的陣列放每個串列的開頭，加上所有鄰居的資料。 有向圖一共 E 筆鄰居，無向圖每條邊在兩端各記一次，一共 2E 筆。空間是 O(V + E)。
| 操作 | 鄰接串列 |
|---|---|
| u → v 有沒有邊 | O(deg(u))，掃過 adj[u] |
| 列出 u 的鄰居 | O(deg(u)) |
| 算 u 的出度 | O(1)，就是 adj[u] 的長度 |
| 算 v 的入度 | O(V + E)，掃過全部串列 |
| 加一條邊 | O(1)，接到尾端 |
| 刪一條邊 | O(deg(u))，先找到它 |
每個串列可以用動態陣列（Python 的 list、C++ 的 vector、Java 的 ArrayList，第 03 課）或鏈結串列（第 06 課）。
動態陣列比較常用：同一個節點的鄰居連續存放，走訪時快取命中率高。
常常要算入度、或要沿著邊「倒著走」的程式，會另外存一份反向圖：radj[v] 列出所有指向 v 的節點。
空間多一倍，換來兩個方向都是 O(deg)。這一課最後的實作就是建反向圖。
互相轉換：無向圖的矩陣變成串列與邊列表
這一次的圖是無向圖，矩陣左右對稱：0 — 1 這條邊同時出現在 m[0][1] 和 m[1][0]。轉成鄰接串列時，矩陣的每個 1 都變成一筆鄰居，所以每條邊在兩端各出現一次；轉成邊列表時只收 u < v 的那一格，每條邊只記一次。轉換要看過整個矩陣，O(V²)。
三種表示法放在一起比
V 是節點數、E 是邊數、deg(u) 是 u 的鄰居數（有向圖指出度）。
| 邊列表 | 鄰接矩陣 | 鄰接串列 | |
|---|---|---|---|
| 空間 | O(E) | O(V²) | O(V + E) |
| u → v 有沒有邊 | O(E) | O(1) | O(deg(u)) |
| 列出 u 的鄰居 | O(E) | O(V) | O(deg(u)) |
| 算 v 的入度（有向圖） | O(E) | O(V) | O(V + E) |
| 加一條邊 | O(1) | O(1) | O(1) |
| 走過所有的邊 | O(E) | O(V²) | O(V + E) |
互相轉換的成本：從邊列表建另外兩種是 O(E)（矩陣還要先花 O(V²) 填 0）；從矩陣轉出去要看過全部 V² 格； 從鄰接串列轉成邊列表是 O(V + E)。
怎麼選看兩件事：圖是稀疏還是稠密，以及程式最常做哪一種操作。
- 稀疏圖用鄰接串列。實際的圖大多是稀疏的：道路網的路口平均只連著三、四條路，社群網站的人也只追蹤一小部分的人。
V = 1,000,000、平均每個節點 10 個鄰居時，鄰接串列約存一千萬筆鄰居；鄰接矩陣要 10¹² 格，用
int存要 4 TB，根本放不進記憶體。 - 稠密圖、或節點很少又常常要問「u 和 v 有沒有直接相連」，用鄰接矩陣。E 接近 V² 時，鄰接串列也要存約 V² 筆， 而且每筆還要額外的空間（串列的結構、指標），矩陣反而比較省，查邊又是 O(1)。
- 只需要把邊整批處理一遍，用邊列表：讀檔、依權重排序、Kruskal。
很多程式會同時存兩種：讀進來是邊列表，建一份鄰接串列給走訪用，必要時再加一份反向圖。多花空間，換取每一種操作都快。
想一想：空間與操作成本
一張無向圖有 V = 1,000 個節點、E = 3,000 條邊。鄰接矩陣與鄰接串列各存多少？
有向圖用鄰接串列存（adj[u] 只列出從 u 出去的邊），下面哪一個操作最慢？
5 個節點的有向圖（不含自環）最多可以有幾條邊？
更緊湊的鄰接串列：兩個陣列
圖建好之後不再改變時，常把鄰接串列壓成兩個一維陣列，叫做 CSR（compressed sparse row）：
to：把 adj[0]、adj[1]、…、adj[V - 1] 的鄰居依序接成一個長度 E 的陣列start：長度 V + 1，start[u]是 u 的鄰居在to裡從哪裡開始；u 的鄰居就是to[start[u]]到to[start[u + 1] - 1]
以前面的有向圖為例：
adj[0] = [1, 2] adj[1] = [3] adj[2] = [1, 3] adj[3] = [4] adj[4] = []
start = [0, 2, 3, 5, 6, 6]
to = [1, 2, 3, 1, 3, 4]
for k in range(start[u], start[u + 1]): # 列出 u 的鄰居
print(to[k])
空間一樣是 O(V + E)，但沒有 V 個獨立的串列物件，鄰居全部連續存放，走訪時記憶體存取很規律。 代價是不能隨意加邊：中間插入一筆，後面全部要往後搬。大型的圖運算（例如稀疏矩陣計算、處理數百萬節點的圖）常用這種格式。
想一想：讀程式、選表示法
下面的程式印出什麼？
m = [[0, 1, 0],
[0, 0, 1],
[1, 1, 0]]
cnt = 0
for u in range(3):
cnt += m[u][1]
print(cnt)
下面的程式把無向圖的邊列表轉成鄰接串列，印出什麼？
edges = [[0, 2], [1, 2], [0, 1]]
adj = [[] for _ in range(3)]
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
print(adj[2], adj[0])
一張 50 個節點、幾乎每兩點之間都有邊的圖，程式要反覆查「u 和 v 之間有沒有直接相連」。用哪一種表示法最合適？
實作：建出反向圖
adj 是一張有向圖的鄰接串列。請完成 reverse_graph：對每一條 u → v，把 u 加進 radj[v]，建好之後 radj[v] 就是「所有指向 v 的節點」，入度就是 radj[v] 的長度。依 u 由小到大處理，印出來的順序才會和預期輸出相同。
重點整理
- 邊列表：一筆一筆列出邊，空間 O(E)；和某個節點有關的問題都要掃全部的邊。適合讀檔、排序邊、Kruskal
- 鄰接矩陣：V × V 表格，空間 O(V²)；查一條邊 O(1)，列出鄰居 O(V)。無向圖左右對稱；權重可能是 0 時要另選「沒有邊」的記號
- 鄰接串列：每個節點一個串列，空間 O(V + E)；列出鄰居 O(deg(u))。無向邊在兩端各記一次；有向圖算入度要掃全部，常另存反向圖
- 稀疏圖用鄰接串列，稠密圖或常查邊的小圖用鄰接矩陣；必要時同時存兩種
- 圖不再改變時，鄰接串列可以壓成
start、to兩個陣列（CSR）
下一課：區間查詢。同樣是「同一份資料、不同的存法讓不同操作變快」，主角換成線段樹與 Fenwick 樹。