上一篇我們從資料夾開始認識 Tree。
像這樣：

Documents
├─ Work
│  ├─ report.pdf
│  └─ meeting.md
│
└─ Personal
   ├─ photos
   └─ notes.md

這種結構很好理解。
每一個節點都有明確的位置：

Documents
   ↓
 Work
   ↓
report.pdf

我們可以很清晰地說：

• Documents 是 Work 的 parent
• Work 是 report.pdf 的 parent
• report.pdf 是 Work 的 child

整個結構從一個 root 往下展開。
但如果今天我們要描述的是捷運路網呢？
Tree 好像又不太適合了。

捷運站之間沒有唯一的「上下關係」

假設有一個非常簡化的捷運系統：

我們可以說：

• A 和 B 相連
• B 和 C 相連
• B 和 D 相連
• C 和 E 相連
• D 和 E 相連

但這時候有一個問題：

誰是誰的 parent？

例如 B 和 D 相連，那我們可以說 B 是 D 的 parent 嗎？
好像可以。
但如果從 D 出發，也完全可以把它理解成 D → B。
另外，從 B 到 E 甚至不只有一種走法，可以是 B → C → E，也可以 B → D → E，這種關係已經不像資料夾那樣有明確的上下階層。

它描述的是：

哪些東西彼此有連接。

這就是 Graph（圖） 真正擅長描述的問題。

Graph 的基本組成：Node 與 Edge

Graph 最基本可以先看成由兩種東西組成：

• Node
• Edge

Node 就是節點。
在比較正式的 Graph Theory 裡，Node 通常也會稱為：

Vertex

之後如果看到這樣的表示法：

G = (V, E)

其中：

V = Vertices
E = Edges

其實就是在描述一張 Graph 裡有哪些節點，以及節點之間有哪些連接。
不過在軟體開發的語境裡，Node 也非常常見。
這個系列後面會以 Node 為主。
在捷運路網裡，每一個站點都可以是一個 Node：

A
B
C
D
E

而站點之間的連接，就是 Edge：

A ─ B
B ─ C
B ─ D
C ─ E
D ─ E

因此剛才的捷運路網：

可以拆成：

Nodes:
A, B, C, D, E

以及：

Edges:
A-B
B-C
B-D
C-E
D-E

這就是 Graph 最基本的模型：

Node 描述有哪些東西，Edge 描述它們之間有什麼關係。

Graph 關心的不是「上下」，而是「連接」

這也是 Tree 和 Graph 很重要的差別。
上一篇看到的資料夾：

Documents
├─ Work
│  ├─ report.pdf
│  └─ meeting.md
└─ Personal
   └─ notes.md

我們很在意：

• 誰是誰的 parent？
• 誰是誰的 child？
• root 在哪裡？
• 某個 subtree 從哪裡開始？

因為 Tree 描述的是一種 hierarchy：

階層關係。

但是捷運路網通常不是這樣。
我們真正想知道的是：

• A 站和哪些站相連？
• A 站能不能到 E 站？
• 從 A 到 E 有幾種走法？
• 哪一條路比較短？

這些問題關心的是彼此之間的連結而不是階層關係。
所以可以先用一個很簡單的方式記住：

• 公司組織 → Tree
• 捷運路網 → Graph

公司組織通常具有明確階層：

CEO
├─ CTO
│  ├─ Engineering Manager
│  └─ Architect
└─ CFO
   └─ Finance Manager

但捷運站只是彼此連接：

沒有誰天生位於誰的「下面」。

Graph 可以描述更自由的關係

Tree 對結構有比較強的限制。
例如一個典型的 rooted tree：

A
├─ B
│  ├─ D
│  └─ E
└─ C

每個 Node 都沿著明確的 parent / child 關係往下延伸，但 Graph 可以更加自由。
例如：

A 可以同時和 B、C、D 產生關係。
B 也可以同時和 A、C 相連。
Graph 不要求所有 Node 一定符合單一的階層。
這也是為什麼它很適合描述：

• 捷運路網
• 道路
• 社群好友
• 航班
• 電腦網路
• 網站連結
• 依賴關係

因為現實世界裡很多關係，本來就沒有那種學長學弟制。
更多是開方式的：

A 和 B 有關係
B 和 C 有關係
A 也可能和 C 有關係

這種比較自由的關係，可以理解成：

arbitrary relationship

也就是：

關係不一定受到固定階層的限制。

Graph 裡甚至可以繞一圈回來

再看看剛才的捷運路網：

如果從 B 出發：

B → C → E → D → B

最後竟然又回到了 B，這種情況叫做 cycle。
也就是：

沿著一系列 Edge 前進之後，可以回到原本的 Node。

這同時也是 Graph 特點，因為在真正的交通網路裡，形成環狀路線其實很正常。
道路也可能：

A → B → C
↑       ↓
E ← D ← ↵

社群關係甚至更加明顯：

Alice ─ Bob
  │      │
Carol ─ David

關係可能彼此交叉，也可能形成很多不同的 cycle。

Tree 為什麼通常不允許 cycle？

假設我們把資料夾改成：

Documents
└─ Work
   └─ Projects
      └─ Documents

然後最後那個 Documents 又指回最上面的 Documents。
就會變成：

Documents
   ↓
Work
   ↓
Projects
   ↓
Documents
   ↓
Work
   ↓
Projects
   ↓
...

我們再也沒有辦法沿著 parent / child 關係一路走到底。
原本清楚的階層也被破壞了，因此 Tree 的一個重要特性就是：

不存在 cycle

英文叫 acyclic，這也是 Tree 能維持明確階層關係的原因之一。

那 Tree 和 Graph 到底是什麼關係？

這裡有一個很重要的觀念：

Tree 本身其實也是 Graph 的一種。

例如：

    A
   / \
  B   C
 / \
D   E

如果只看 Node：

A
B
C
D
E

再看 Edge：

A-B
A-C
B-D
B-E

它完全符合 Graph 的基本概念。
也就是 Node + Edge，只是 Tree 又多了一些限制。
以最常見的無向樹來說，它會是 connected + acyclic。
你可以這樣理解：

所有 Node 彼此都能透過某條路徑連接，而且不存在 cycle。

如果再指定一個 root：A。
我們就可以進一步建立：

parent
child
depth
subtree

這些上一篇介紹過的 Tree 概念。
所以比較精確地說：

Tree 是受到更多結構限制的 Graph。

不是 Tree 和 Graph 使用完全不同的東西。
它們都可以由 Node + Edge 來理解。
差別在於：

Tree 對 Node 和 Edge 之間能形成什麼關係，有更多限制。

可以把它想成：

Graph
└─ Tree

Tree 是 Graph 家族裡的一種特殊形式。

為什麼不能硬把捷運路網畫成 Tree？

其實我們當然可以選一個站當 root。
例如從 A 開始：

A
└─ B
   ├─ C
   │  └─ E
   └─ D

看起來真的變成 Tree 了，但要注意一個前提。
原本的捷運路網是：

Tree 版本卻變成：

A
└─ B
   ├─ C
   │  └─ E
   └─ D

這裡少掉了一條關係 D ─ E，為了讓資料符合 Tree，我們不得不丟掉原本存在的連接。
這就是問題所在。

不是我們能不能把資料畫成 Tree，而是 Tree 能不能保留問題真正重要的關係。

如果 D ─ E 代表一條真的存在的捷運連接，那它就是問題的一部分。
不能因為 Tree 比較容易理解，就假裝這條路不存在。

資料結構不是把資料硬塞進某個形狀

這也再次回到這個系列一直在強調的事情：

資料結構是一種問題表述

我們不是先決定「我今天想用 Tree」，然後想辦法把現實世界塞進 Tree。
在這之前要先問：

這個問題裡真正重要的是什麼？

如果問題是「誰屬於誰？」，那用 Tree 很合理。
例如：

• 資料夾
• 公司組織
• 分類目錄
• DOM 的階層

如果問題變成「誰和誰有連接？」，Graph 會更加適合。
例如：

• 捷運
• 道路
• 好友關係
• 網路拓樸
• 模組依賴

真正決定資料結構的，是我們想保留的關係。

認出 Graph 之後，下一個問題是怎麼保存它

到目前為止，我們介紹過：

• Queue
• Priority Queue
• Stack
• Hash Map
• Tree
• Graph

前面的 Queue、Priority Queue、Stack，很大一部分都在描述：

下一個要處理誰？

Hash Map 關心的是：

知道 key 之後，怎麼直接找到資料？

Tree 和 Graph 則把焦點移到資料之間的關係：

Tree  → 誰屬於誰？
Graph → 誰和誰相連？

現在，我們已經可以在紙上把捷運路網畫成 Node 和 Edge：

但程式真正能保存的是 Array、Object、Map 這類資料，而不是紙上的「點」和「線」。

所以接下來真正要回答的是：

同一張 Graph，到了程式裡應該怎麼表示？

而不同的表示方式，又會讓哪些操作變得簡單或困難？

下一篇，我們就從這個問題開始。