前幾天我們一直用 Graph 描述「東西之間怎麼連在一起」。
例如捷運路網：

我們在意的是：

從 A 能不能走到 F？
哪條路比較短？
哪條路花的時間比較少？

但生活中還有另一種很常見的關係。
有些事情不是「彼此有連接」就結束了，還需要：

A 必須先完成，B 才能開始

這時候，Graph 裡的「方向」就變得非常重要。

有些事情真的不能顛倒順序

假設今天要做一道菜。
流程可能是：

買食材 → 備料 → 烹煮 → 上桌

你不能先上桌，再去烹煮。
也不能先烹煮，再去買食材。
這些步驟之間存在明確的先後關係：

這和捷運路網不一樣，捷運站 A 和 B 相連，通常表示 A ↔ B，你可以從 A 到 B，也可以從 B 回到 A。

但做菜流程中的 買食材 → 備料，不是在說買食材和備料彼此有關，而是在說：

備料依賴買食材先完成

這就是今天要談的：

Directed Graph（有向圖）

Graph 不只是「有沒有連接」

前面介紹 Graph 時，我們可以先把一條 Edge 理解成：

A ─ B

代表 A 和 B 之間存在某種關係，但現在我們需要更精確一點。
如果關係本身有方向，可以表示成：

A → B

這條 Edge 就不只是「A 跟 B 有關」。
它還表示：

關係是從 A 指向 B

像 買食材 → 備料 我們可以理解成：

買食材完成後，才能進行備料

方向本身，就是問題的一部分。

Directed Graph 是什麼？

如果 Graph 裡的 Edge 帶有方向，我們就稱它為：

Directed Graph 有向圖

例如：

A → B
A → C
B → D
C → D

這裡不能單純把 A → B 看成 A ─ B，因為 A → B 並不自動代表 B → A。

考駕照也有方向

以聯結車駕照就是很典型的例子。
假設：

普通車駕照 → 大客車駕照 → 聯結車駕照

意思是：

• 先取得普通車駕照，才能有資格去考大客車駕照
• 先取得大客車駕照，才能有資格去修聯結車駕照

如果畫成 Graph：

這時候每一張駕照都是 Node，而 普通車駕照 → 大客車駕照 這條 Edge 描述的不是「兩個駕照有關」。
它描述的是：

一個先決條件，也就是依賴關係 (dependency)

Dependency：真正重要的是「誰依賴誰」

在很多工程問題裡，我們會一直碰到 dependency。
例如專案工作可能是：

需求確認 → API 設計 → 後端實作
                  ↓
               前端串接
                  ↓
               整合測試

或者：

這些事情都不是隨便選一件開始做，某些工作必須等前面的工作完成。
所以我們想描述的是 A → B 代表：

B 依賴 A

也可以換個角度說 A 是 B 的前置條件。

Build pipeline 也是一張 Directed Graph

軟體工程裡更常看到這種關係。
假設一個簡化的 build pipeline：

看起來很像一條直線。
但真實情況可能更像：

這裡 Lint 和 Test 都依賴 Install。
而 Build 可能要求兩者都成功：

• Lint → Build
• Test → Build

這時候 Graph 就比單純的一串 Array 更容易表達這種關係。
因為我們描述的不只是：

第一步
第二步
第三步

還有：

哪些工作依賴哪些工作？

有 dependency，不代表一定只有一條路

假設：

買食材 → 洗菜
買食材 → 切肉
洗菜 → 烹煮
切肉 → 烹煮

畫成圖：

這代表什麼？
買完食材後洗菜和切肉，不一定需要互相等待，它們可以各自開始。
真正需要等待的是烹煮，因為它同時依賴兩件事情完成。

所以 dependency Graph 不等於單純的 sequential process。
它可以有分支，也可以重新匯合。

incoming edge 和 outgoing edge

當 Graph 有方向後，我們也可以開始描述 Edge 是「進來」還是「出去」。
假設：

A → C
B → C
C → D

對 C 而言 A → C 和 B → C，是它的 incoming edges。
因為 Edge 指向 C。

而 C → D，則是 C 的 outgoing edge。
因為 Edge 從 C 指出去。

可以簡單理解成：

• incoming edge：有哪些東西指向我？
• outgoing edge：我又指向哪些東西？

以 dependency 問題為例

假設：

對「烹煮」這個 Node 來說，它有兩條 incoming edge。
這通常可以理解成：

烹煮有兩個前置 dependency

如果這兩件事情都還沒完成，那麼烹煮就不能開始。
反過來看 烹煮 → 上桌，這是一條 outgoing edge。
代表：

當烹煮完成之後，還有別的工作依賴它

方向會改變 Graph 的語意

比較一下，沒有方向的 Graph：

A ─ B

比較像是在說：

A 和 B 有連接

有方向的 Graph：

A → B

則是在說：

A 到 B 存在一個特定方向的關係

它可能代表：

A prerequisite of B

也可能代表：

A calls B
A sends data to B
A links to B
A must finish before B

所以：

Edge 不只是「有沒有關係」，還可以攜帶關係的方向

程式裡可以怎麼表示？

假設我們有：

買食材 → 備料 → 烹煮 → 上桌

使用 Adjacency List，可以寫成：

const graph = new Map([
  ["買食材", ["備料"]],
  ["備料", ["烹煮"]],
  ["烹煮", ["上桌"]],
  ["上桌", []],
]);

這裡：

graph.get("備料")

得到：

["烹煮"]

意思是：

從「備料」這個 Node，有一條 outgoing edge 指向「烹煮」

如果是：

const graph = new Map([
  ["買食材", ["洗菜", "切肉"]],
  ["洗菜", ["烹煮"]],
  ["切肉", ["烹煮"]],
  ["烹煮", ["上桌"]],
  ["上桌", []],
]);

那麼 Graph 就是：

同一個 Graph 裡，有些工作可以平行進行，有些則必須等待。

這跟前面的 Graph 有什麼不同？

前面講捷運時，我們關心的是：

可以往哪裡走？

今天講 dependency 時，我們開始關心：

哪些事情必須先完成？

兩者都可以用 Graph。
但 Edge 的語意完全不同。
捷運的 A ─ B 表示：

兩個地方之間有連接

Dependency 的 A → B 表示：

B 的執行受到 A 的約束

所以同樣是 Graph，真正重要的從來不只是畫一堆 Node 和 Edge。

而是：

你到底用這些 Edge 描述什麼關係？

為什麼這件事情很重要？

因為真實世界很多問題，都不是「找一條路」而已。
我們還會遇到：

• 哪些事情現在可以開始？
• 哪些事情還必須等待？
• 一個工作完成後，哪些工作會被解鎖？
• 整個專案到底應該按照什麼順序執行？

例如：

• Build pipeline
• package dependency
• 考駕照順序
• 專案排程

甚至是我們之後會碰到的 reactive dependency graph。
它們背後其實都在問類似的事情：

當一件事情依賴另一件事情時，執行順序應該怎麼決定？

今天不只是多認識一種 Graph，而是替關係加上方向約束

從 Day 7 開始，我們已經知道 Graph 可以描述任意關係。
今天則再往前一步探索，不只問誰和誰有關？
還要問這個關係有沒有方向？
一旦 Edge 有了方向，就可以開始描述：

dependency
prerequisite
execution order
data flow

Graph 就不再只能描述地圖，也可以成為一張：

工作的依賴圖

小結

今天可以先記住：

• Directed Graph：Edge 有方向
• Edge 一但有方向：A → B 關係成立，不等於 B → A也成立
• dependency：某件事情需要另一件事情先完成
• incoming edge：指向某個 Node 的 Edge
• outgoing edge：從某個 Node 指出去的 Edge

其中最重要的是：

Graph 不只可以描述「誰和誰相連」，還可以描述「誰必須先於誰」

留給下一篇的問題

如果 dependency 是：

A → B
B → C

我們很容易理解：

A 完成後做 B
B 完成後做 C

但如果又多出一條 dependency：

C → A

整張 Graph 就會變成：

按照今天對箭頭的定義：

B 等 A
C 等 B
A 又等 C

每一條 dependency 單獨看都可能有理由，但當它們連在一起之後：

整個流程還有辦法找到第一件可以開始的事情嗎？

當 dependency 繞了一圈回到原點，我們就遇到了下一篇要處理的問題：

Circular Dependency