Terry Yao's Blog

algorithmsGraph Algorithms 圖演算法（下）：拓撲排序與工程應用
algorithms

Graph Algorithms 圖演算法（下）：拓撲排序與工程應用

閱讀時間約 6 分鐘

cover

如果你還沒看過 上篇的最短路徑，建議先看。這篇講拓撲排序和圖演算法的工程應用。

有依賴關係，就有拓撲排序

拓撲排序解決的是「有依賴關係的東西，該按什麼順序處理」。你每天跑的 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 檢查，底層就是這個。

🎬 互動視覺化： DFS — Kahn’s 本質就是一趟 BFS，看著佇列逐層吐節點，就能理解「入度歸零才進隊」是怎麼把 DAG 攤成一條線的。

工程實戰：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', []],
]);
 
// 邊是「package → 它依賴的套件」，入度為 0 的是「沒人依賴」的 express，
// 所以 Kahn's 會先吐出 express：
const order = topologicalSort(packages);
// ['express', 'body-parser', 'cookie-parser', 'raw-body', 'content-type', 'cookie']
 
// 但安裝要「被依賴的先裝」，剛好相反——把結果反轉才是安裝順序：
const installOrder = order.reverse();
// ['cookie', 'content-type', 'raw-body', 'cookie-parser', 'body-parser', 'express']

這裡藏著一個容易踩的雷：拓撲排序的方向取決於你怎麼定義邊。這張圖的邊是「A 依賴 B」，直接排序會先吐出沒人依賴的 express；但安裝要反過來——先裝沒有依賴的 raw-body、content-type、cookie，最後才裝 express。邊的方向定反了，整個順序就顛倒，所以 npm 這種場景要嘛把邊建成「B 先於 A」，要嘛把結果反轉。

其他拓撲排序場景：

  • Webpack/Vite module bundling：決定 import 順序
  • CI/CD pipeline：build → test → deploy
  • 資料庫 migration：哪個 migration 先跑

圖演算法選擇指南

你想做什麼用什麼
計算兩點最短路徑A*（地圖導航）
計算一點到所有點Dijkstra（網路路由）
有負權重Bellman-Ford（套利偵測）
所有點對距離Floyd-Warshall
決定安裝/執行順序拓撲排序
偵測循環依賴拓撲排序
找社群/連通元件BFS / DFS

什麼時候不需要圖演算法

問自己一個問題：你的資料之間有「關係」嗎？

圖演算法是用來處理「多對多的關係」的。如果你的資料關係是一對多（樹）或沒有關係（列表），就不要硬套圖。

進階圖論（MST、SCC、二分圖）請看 進階圖論。

每次跑 npm install 等很久的時候，想想它正在解一個拓撲排序問題。然後你會發現等待變得更痛苦了，因為你知道那只是 O(V+E)。

接下來往哪走

關係圖譜

反向連結