如果你還沒看過 上篇的最短路徑，建議先看。這篇講拓撲排序和圖演算法的工程應用。
先講結論
拓撲排序解決的是「有依賴關係的東西，該按什麼順序處理」。你每天跑的 npm install、CI/CD pipeline、甚至大學選課——底層都是拓撲排序。
拓撲排序：誰先誰後
把 DAG（有向無環圖）的節點排成一條線，讓所有的邊都從左指向右。
課程依賴：
微積分 → 線性代數 → 機器學習
程式設計 → 資料結構 → 演算法
拓撲排序結果：微積分, 程式設計, 線性代數, 資料結構, 機器學習, 演算法
Kahn’s Algorithm（BFS 做法）
核心想法：誰沒有依賴（入度為 0），誰就先做。
function topologicalSort(graph: Map<string, string[]>): string[] {
const inDegree = new Map<string, number>();
for (const node of graph.keys()) inDegree.set(node, 0);
for (const [, deps] of graph) {
for (const dep of deps) {
inDegree.set(dep, (inDegree.get(dep) ?? 0) + 1);
}
}
const queue: string[] = [];
for (const [node, degree] of inDegree) {
if (degree === 0) queue.push(node);
}
const result: string[] = [];
while (queue.length > 0) {
const u = queue.shift()!;
result.push(u);
for (const v of graph.get(u) ?? []) {
const newDegree = inDegree.get(v)! - 1;
inDegree.set(v, newDegree);
if (newDegree === 0) queue.push(v);
}
}
if (result.length !== graph.size) {
throw new Error('存在循環依賴！');
}
return result;
}最後那個檢查很重要：如果結果數量不等於節點數量，代表有環——也就是循環依賴。ESLint 的 circular dependency 檢查，底層就是這個。
工程實戰：npm 怎麼決定安裝順序
npm install 背後就是拓撲排序。每個套件有 dependencies，npm 要決定先裝哪個：
const packages = new Map<string, string[]>([
['express', ['body-parser', 'cookie-parser']],
['body-parser', ['raw-body', 'content-type']],
['cookie-parser', ['cookie']],
['raw-body', []],
['content-type', []],
['cookie', []],
]);
const installOrder = topologicalSort(packages);
// ['raw-body', 'content-type', 'cookie', 'body-parser', 'cookie-parser', 'express']先裝沒有依賴的（raw-body、content-type、cookie），再裝依賴它們的，最後裝 express。
其他拓撲排序場景：
- Webpack/Vite module bundling：決定 import 順序
- CI/CD pipeline：build → test → deploy
- 資料庫 migration：哪個 migration 先跑
圖演算法選擇指南
| 你想做什麼 | 用什麼 |
|---|---|
| 計算兩點最短路徑 | A*（地圖導航） |
| 計算一點到所有點 | Dijkstra（網路路由） |
| 有負權重 | Bellman-Ford（套利偵測） |
| 所有點對距離 | Floyd-Warshall |
| 決定安裝/執行順序 | 拓撲排序 |
| 偵測循環依賴 | 拓撲排序 |
| 找社群/連通元件 | BFS / DFS |
什麼時候不需要圖演算法
問自己一個問題：你的資料之間有「關係」嗎？
- 純粹的列表/集合：用 Array 或 Hash Table
- 明確的父子關係（樹）：用 Tree 的遍歷
- 只需排序：用 排序演算法
圖演算法是用來處理「多對多的關係」的。如果你的資料關係是一對多（樹）或沒有關係（列表），就不要硬套圖。
進階圖論（MST、SCC、二分圖）請看 進階圖論。
每次跑 npm install 等很久的時候，想想它正在解一個拓撲排序問題。然後你會發現等待變得更痛苦了，因為你知道那只是 O(V+E)。