上一篇我們用捷運路網理解 Graph。
例如有幾個站點：

如果把它看成 Graph：

• 每個車站是一個 node
• 站與站之間的連接是一條 edge

畫出來很直覺。
我們可以直接看到：

A 連到 B
A 連到 D
B 連到 C
B 連到 E
D 連到 E
E 連到 F
C 連到 F

但到了程式裡，就會遇到一個很實際的問題：

這些「線」到底要怎麼存？

因為程式真正能保存的，還是 Array、Object、Map 之類的資料。
Graph 本身是一種關係模型，真正寫進程式時，我們還必須決定：

要用什麼資料結構表示這些關係？

這就是今天要談的 Graph 表示方式。

同一張 Graph，可以有不同的表示方式

先固定使用這張 Graph：

它的連接關係是：

A ↔ B
A ↔ D

B ↔ C
B ↔ E

C ↔ F

D ↔ E

E ↔ F

這裡先把捷運站之間的連接視為雙向。
例如：

A ↔ B

代表從 A 可以到 B，也可以從 B 回到 A。
接下來，我們來看看程式可以怎麼描述這張 Graph。

方法一：Adjacency List

第一種很常見的方法叫做：

Adjacency List

中文通常翻成「鄰接串列」或「鄰接表」。
它的想法很直接：

對每一個 node，記錄它直接連到哪些 node。

例如剛才的捷運圖可以寫成：

A → B, D
B → A, C, E
C → B, F
D → A, E
E → B, D, F
F → C, E

如果用 JavaScript，可以寫成：

const graph = new Map([
  ["A", ["B", "D"]],
  ["B", ["A", "C", "E"]],
  ["C", ["B", "F"]],
  ["D", ["A", "E"]],
  ["E", ["B", "D", "F"]],
  ["F", ["C", "E"]],
]);

這時如果想知道：

B 可以直接去哪裡？

就可以取得：

graph.get("B");

結果是：

["A", "C", "E"]

也就是：

B → A
B → C
B → E

Adjacency List 並沒有真的在程式裡保存一條「線」。
它保存的是：

每個 node 的鄰居是誰。

靠這些鄰接關係，我們就能把整張 Graph 還原出來。

「鄰居」就是 Graph 很重要的資訊

假設現在我們人在 B 站，我們想知道下一站可以去哪裡。
我們其實不需要知道整張捷運圖長什麼樣子？
我們只需要知道：

B 的鄰居有哪些？

在 Adjacency List 中，這個問題非常直覺：

graph.get("B");

得到：

A
C
E

這個特性很實用，因為我們開始在 Graph 上搜尋時，經常做的事情就是：

目前在哪個 node？
→ 它有哪些 neighbor？
→ 下一步要走去哪裡？

Adjacency List 的表示方式其實已經很接近我們之後走訪 Graph 時的思考方式。

方法二：Adjacency Matrix

另一種常見的 Graph 表示方法叫做：

Adjacency Matrix

中文應該叫「鄰接矩陣」。
這次我們不替每個 node 保存鄰居清單，而是直接建立一張表：

任意兩個 node 之間有沒有 edge？

例如同樣這六個站：

A
B
C
D
E
F

我們可以建立：

    A B C D E F

A   0 1 0 1 0 0
B   1 0 1 0 1 0
C   0 1 0 0 0 1
D   1 0 0 0 1 0
E   0 1 0 1 0 1
F   0 0 1 0 1 0

每一格代表：

兩個 node 之間有沒有連接？

例如：

A ↔ B = 1

表示 A 和 B 有 edge。
而：

A ↔ C = 0

表示 A 和 C 沒有直接連接。
如果用 JavaScript，可以表示成：

const nodes = ["A", "B", "C", "D", "E", "F"];

const matrix = [
  [0, 1, 0, 1, 0, 0], // A
  [1, 0, 1, 0, 1, 0], // B
  [0, 1, 0, 0, 0, 1], // C
  [1, 0, 0, 0, 1, 0], // D
  [0, 1, 0, 1, 0, 1], // E
  [0, 0, 1, 0, 1, 0], // F
];

假設：

A = index 0
E = index 4

那麼要知道 A 和 E 有沒有直接相連，就可以看：

matrix[0][4];

結果是：

0

代表沒有直接連接。

而：

matrix[0][1];

會得到：

1

代表 A 和 B 有 edge。

兩種表示方式，其實在回答不同形式的問題

Adjacency List 看起來像：

A → B, D
B → A, C, E
C → B, F
...

所以它很簡單地回答：

A 的鄰居有哪些？

而 Adjacency Matrix 長得像：

    A B C D E F
A   0 1 0 1 0 0
B   1 0 1 0 1 0
...

所以它很自然地回答：

A 和 E 之間有沒有直接連接？

注意，這裡不是說：

• Adjacency List 只能回答第一種問題
• Adjacency Matrix 只能回答第二種問題

兩種表述方式都可以描述同一張 Graph。
差別在於：

某些操作，在某種表述方式裡會比較合適

Data Structure 不只是「資料放在哪裡」

Day 1 我們提過：

資料結構不是單純拿來裝資料的容器，而是我們選擇如何描述問題

Graph 把這件事情表現得非常清楚。
因為同一個現實世界問題：
捷運站之間的連接，可以先抽象成 Graph。

但 Graph 還不是最後一步，到了程式裡，我們還要再決定：

Graph
↓
Adjacency List？
Adjacency Matrix？

也就是說，問題的表示其實可以有好幾層：

現實世界
↓
Graph
↓
程式中的 Graph Representation

每做一次選擇，都會影響後面的操作方式。

為什麼不永遠選一種就好？

你可能會開始有一個疑問：

既然兩種方法都能表示 Graph，那為什麼不選一種大家固定用就好？

原因是：

表示方法本身就有 trade-off

例如 Adjacency List 只需要明確列出真正存在的連接。
如果 A 只連到：

B
D

那就只需要保存：

A → B, D

沒有連接的站，不需要特別寫出來。
但 Adjacency Matrix 不一樣，就算 A 和其他很多站都沒有連接，那些位置仍然存在：

A → B = 1
A → C = 0
A → D = 1
A → E = 0
A → F = 0

反過來說，如果你的問題經常是在問：

A 和 F 有直接連接嗎？

Matrix 這種表示方式就非常直觀：

找到 A 的 row
找到 F 的 column
看那一格

所以沒有哪一種表示方法永遠比較好。
真正的考量仍然是：

我們最常需要做什麼操作？

這其實和前面幾天是同一件事

回頭看前幾篇：

• Queue → 我在意誰先被處理
• Stack → 我在意誰最後加入
• Hash Map → 我在意能不能透過 key 找到 value
• Tree → 我在意 parent / child 的階層關係
• Graph → 我在意 node 之間任意的連接關係

到了今天，我們又更進一步：

Graph 已經決定了「關係是什麼」
Graph Representation 則決定了「這些關係在程式裡怎麼被保存」

這兩件事情很接近，但並不完全相同。

Graph 是模型，Adjacency List 是表示方法

假設有人問：

這個捷運系統是不是 Graph？

那是肯定的阿，但如果改問：

這張 Graph 在程式裡怎麼存？

答案就不一定只有一個。
可能是 Adjacency List。
也可能是 Adjacency Matrix。
甚至實際系統裡還可能有其他更適合需求的表示方式。

所以 Graph 比較像是在說：

資料之間的關係是什麼？

而 Adjacency List 和 Adjacency Matrix 是在說：

我們決定怎麼把這些關係放進程式裡？

Representation 會影響 Algorithm

這裡先留下一個非常重要的觀念：

Algorithm 並不是完全獨立於 Data Structure 存在的

我們下一步如果要做從 A 出發找到 F，就必須不斷知道：

目前這個 node 可以走到哪些 node？

而 Graph 的 representation，就會影響我們取得這些資訊的方式。
這也是為什麼在真正開始介紹 Graph Search 以前，我們要先理解：

Graph 到底怎麼存在程式裡？

因為接下來要做的搜尋，全部都建立在這些表示方式之上。

今天先記住一件事

如果只要記得今天的一個觀念，那就是：

同一張 Graph，可以有不同的表示方法

例如：

Graph
├─ Adjacency List
└─ Adjacency Matrix

它們描述的是同一組 node 與 edge。
但它們保存資料的方式不同，因此擅長的操作也不同。
這正是 Data Structure 最核心的思考之一：

Representation is a trade-off

我們不是單純在處理這份資料的存放問題，還有預先考量準備怎麼使用它？

把 Graph 存下來之後，我們還要決定怎麼走

現在我們已經知道：

• node 是什麼
• edge 是什麼
• Graph 怎麼表示

例如使用 Adjacency List 時：

graph.get("A");

會得到 ["B", "D"]，這告訴我們：

A 的鄰居是 B 和 D。

但它沒有告訴我們：

• 應該先走 B，還是先走 D？
• 走到 B 之後，下一步又要去哪裡？
• 遇到已經走過的 node，要不要再走一次？
• 走到沒有新鄰居的地方，又該怎麼辦？

Graph 不像 Array，本身沒有天然的：

第一個
第二個
第三個

表示方式幫我們保存了關係，卻沒有替我們決定走訪順序。
所以，要真的走過一張 Graph，我們還需要一套 traversal strategy：

下一個要拜訪哪個 node？

其中一種很直覺的策略是：

選一條路持續深入，直到走不下去，再回到上一個岔路口。

這種走法，就會帶我們進入下一篇的主題：

Depth-First Search