上一篇我們開始把「事情必須按照先後順序完成」畫成有向圖。
例如：

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

箭頭代表 dependency：

A → B

可以理解成：

B 必須等 A 完成之後，才能開始

如果所有 dependency 都像上面這樣一路往前，事情其實不複雜。
比較棘手的情況是：

A → B → C → A

因為這次，我們沿著箭頭走了一圈之後，又回到了原點。
這就是今天要談的：

循環 Cycle

一個很荒謬，但其實很常見的問題

想像你今天要去公部門辦兩個手續。
辦 A 時，承辦人告訴你：

要先完成 B，才能辦 A

於是你跑去辦 B。
結果另一個窗口告訴你：

要先完成 A，才能辦 B

現在就變成：

B → A
A → B

這樣很難辦阿

這不就變成先有雞還先有蛋的問題了嗎？

根本沒有任何一件事情可以先開始

這就是 circular dependency，也就是「循環依賴」。

從 Directed Graph 看 Cycle

假設我們有三件工作：

A → B
B → C
C → A

畫在一起就是：

如果從 A 開始沿著 dependency 往下走：

A
↓
B
↓
C
↓
A

最後又回到了 A。
這種「從某個 node 出發，沿著 edge 前進後，又回到原本 node」的結構，就是：

Cycle 循環

在 Directed Graph 中，我們特別關心箭頭方向。
例如：

A → B
B → C
C → A

符合一個 cycle。
但：

A → B
A → C

明顯不是。
雖然 B 和 C 都跟 A 有關係，但沒有辦法沿著箭頭繞一圈回來。
所以判斷 Cycle 時，不能只問：

這幾個 node 有沒有連在一起？

還要確認：

沿著 edge 的方向前進，有沒有可能再次走回自己？

Cycle 本身不一定是錯的

這裡有一個很重要的認知，Graph 裡面存在 Cycle，本身並不代表 Graph 有問題。
例如捷運路網：

形成一個環狀路線完全合理。
社群關係也可能是：

Alice → Bob
Bob → Carol
Carol → Alice

這同樣沒有什麼問題。
甚至我們在前面介紹 Graph 時，就說過：

Graph 可以描述任意關係，Cycle 是很自然的結構

問題在於：

當 edge 表示「必須先完成」時，Cycle 的語意就變了

如果 A → B 表示：

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

那麼：

A → B → C → A

就代表：

B 等 A
C 等 B
A 又等 C

於是整個 dependency chain 沒有起點。
所以更精確地說：

Cycle 不一定有問題，但 Dependency Graph 裡的 Cycle 往往是一個警訊

Package dependency 也會遇到一樣的問題

這種事情在工程裡非常常見。
假設有三個 module：

user
order
payment

一開始設計可能是：

user → order
order → payment

意思是 order 使用 user 提供的功能，而 payment 又依賴 order。
結果後來因為某個需求，user 裡又想使用 payment：

user → order
order → payment
payment → user

現在 dependency graph 就變成：

user
  ↓
order
  ↓
payment
  ↓
user

Circular dependency 出現了。

為什麼 Circular Dependency 會讓系統變麻煩？

直覺上可能會覺得：

反正最後大家都有載入，不就好了？

但 dependency 通常不只是「知道彼此存在」。
它可能代表：

• 初始化
• 載入
• 編譯
• 建置
• 計算
• 部署

都有先後順序。
例如：

A 必須初始化後，B 才能初始化
B 必須初始化後，C 才能初始化
C 又要求 A 尚未初始化前提供某個結果

系統就很難回答：

到底誰先？

有些 runtime 或 module system 可以處理部分 circular dependency，但這並不代表 Cycle 不重要。
因為 Cycle 仍然可能造成：

• 初始化順序不明確
• 部分 module 尚未準備完成
• 拿到 undefined / incomplete state
• 架構 coupling 增加

因此 Circular Dependency 往往也是一種架構感知。

它可能暗示：

這幾個 module 的責任邊界是不是切錯了？

Dependency Graph 真正在意的是「能不能開始」

回頭看上一篇的例子：

我們可以立刻找到一個起點買食材，因為它不需要等任何前置工作。
完成之後備料就可以開始，再來烹煮，最後才是上桌。

所以 dependency graph 裡，一個很重要的問題就是：

哪些 node 現在沒有任何未完成的 dependency？

如果有，我們至少知道某些事情可以開始。
但看看：

A → B → C → A

如果箭頭表示「前者必須先完成」，那麼：

A 等 C
B 等 A
C 等 B

每個人都有尚未完成的 dependency。
因此：

沒有任何 node 可以先開始

這就是 Cycle 在 dependency 問題中最麻煩的地方。

Cycle Detection：先確認問題到底有沒有解

既然 Cycle 會讓 dependency 無法正常往前推進，那麼在很多系統裡，我們會需要做一件事：

Cycle Detection

也就是：

Graph 裡面到底有沒有 Cycle？

這個問題其實非常常見。
例如：

• Build system
• Package manager
• Module dependency
• 課程先修關係
• 工作排程
• CI/CD pipeline

都可能需要檢查 dependency graph。
因為在真正安排順序之前，我們最好先確認：

這些 dependency 本身是不是互相矛盾的？

怎麼發現自己繞回去了？

先不用急著背演算法，我們可以直接從「走 Graph」的角度想。
假設：

A → B → C → D

我們從 A 開始：

A
↓
B
↓
C
↓
D

一路都沒有重複遇到正在處理中的 node，沒問題。

但如果是：

A → B → C → A

我們走到最後 C → A 階段，此時發現：

A 明明還在這條 dependency path 裡，現在卻又遇到 A

我們繞回去了，也就存在 Cycle。

這跟前面的 visited 有點像，但又不完全一樣

Day 9 講 DFS 時，我們使用過：

visited

因為在 Graph 裡探索時，我們通常不希望同一個 node 一直重複走。
但 Cycle Detection 還需要再多想一層。

假設 Graph 是：

D 會被不同路徑碰到，但這不代表有 Cycle。
D 被走到兩次，只表示 B 和 C 都依賴 D。
真正的 Cycle Detection 關心的是：

我現在走的這條路上，有沒有再次遇到一個還沒走完的 node？

所以概念上可以區分 visited 代表：

我以前看過這個 node。

而另一種狀態則代表：

這個 node 現在還在目前的 dependency path 裡

如果沿著 dependency 繼續走時，又碰到「正在這條 path 裡」的 node：

A → B → C → A

那麼 Cycle 就出現了，這也是 DFS 很自然可以拿來做 Cycle Detection 的原因之一。

不一定要先會寫 Cycle Detection

到這裡，其實不需要立刻寫出完整實作。
這系列更重要的是先建立一個觀念：

不同 Graph 問題，關心的其實是不同性質

前面我們問過：

能不能走到？

所以有 DFS、BFS。

接著問：

哪條路成本最低？

所以開始需要 Weighted Graph 與 Dijkstra。

現在是在問：

dependency 本身有沒有矛盾？

於是我們開始關心 Cycle。

同樣都是 Graph，問題不同，演算法也就不同。

今天先記住這件事

Graph 裡有 Cycle，不一定代表錯誤。
但如果有向圖的 edge 表示：

• 先完成
• 依賴
• 前置條件

那麼：

A → B → C → A

就可能代表：

A 等 C
C 等 B
B 又等 A

最後：

所有人都在等，但沒有人能先開始

因此在 Dependency Graph 裡，Cycle Detection 不只是在找圖形上的圈。
它檢查的重心放在：

這組 dependency 是否互相矛盾，導致整個流程無法開始

留給下一篇的問題

假設我們已經確認下面這張 Dependency Graph 沒有 Cycle：

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

這代表 dependency 沒有形成互相等待。
但它仍然沒有直接告訴我們：

• 第一件事要做什麼？
• 接下來要做什麼？
• 怎麼確保執行順序沒有違反任何 dependency？

排除 Cycle，只是確認這個問題有機會被安排。
接下來要思考的是：

在所有先後限制之下，工作應該按照什麼順序執行？

這就是下一篇要處理的問題。