[algorithms] Graph Algorithms 圖演算法

視覺化概覽

flowchart TD
    A["初始化：起點距離=0\n其餘=∞"] --> B["從 Priority Queue\n取出距離最小的節點 u"]
    B --> C{"u 已訪問過？"}
    C -->|"是"| B
    C -->|"否"| D["標記 u 為已訪問"]
    D --> E["遍歷 u 的所有鄰居 v"]
    E --> F{"dist[u] + weight(u,v)\n< dist[v]？"}
    F -->|"是"| G["更新 dist[v]\n加入 Priority Queue"]
    F -->|"否"| H["跳過"]
    G --> I{"還有未訪問節點？"}
    H --> I
    I -->|"是"| B
    I -->|"否"| J["完成！dist[] 為最短路徑"]

你每天都在用圖演算法

你用 npm install 裝過套件嗎？npm 怎麼決定先安裝哪個套件？拓撲排序。你用過 Google Maps 導航嗎？它怎麼算出最短路線？Dijkstra / A*。你在 LinkedIn 看過「你可能認識的人」嗎？BFS（廣度優先搜尋）。

圖演算法不只是學術題目，它藏在你每天用的工具裡：

工程場景	對應演算法
npm install / pnpm install 套件安裝順序	拓撲排序
Google Maps / Apple Maps 路線規劃	Dijkstra + A*
社群網站「你可能認識的人」	BFS / DFS
網路路由（OSPF 協定）	Dijkstra
任務排程（CI/CD pipeline）	拓撲排序 + 關鍵路徑法
git merge-base 找共同祖先	BFS on DAG
資料庫 query optimizer 的 join 順序	圖遍歷 + 動態規劃

最短路徑問題

從 A 到 B 最短要走多遠？

    1 ---4--- 2
    |         |
    2         1
    |         |
    3 ---3--- 4

Dijkstra 演算法

貪心策略：每次選擇目前最近的點。

從 1 出發：
1. dist = [0, ∞, ∞, ∞]  ← 1 確定
2. 更新 1 的鄰居：dist = [0, 4, 2, ∞]
3. 選最小的 3：dist[3] = 2 確定
4. 更新 3 的鄰居：dist = [0, 4, 2, 5]
5. 選最小的 2：dist[2] = 4 確定
6. 更新 2 的鄰居：dist = [0, 4, 2, 5]
7. 選最小的 4：dist[4] = 5 確定

實作（Priority Queue）

int[] dijkstra(Graph g, int source) {
    int[] dist = new int[V];
    Arrays.fill(dist, INF);
    dist[source] = 0;
 
    // (距離, 節點)
    PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[0]-b[0]);
    pq.offer(new int[]{0, source});
 
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int d = curr[0], u = curr[1];
 
        if (d > dist[u]) continue;  // 已有更短路徑
 
        for (Edge e : neighbors(u)) {
            int newDist = dist[u] + e.weight;
            if (newDist < dist[e.to]) {
                dist[e.to] = newDist;
                pq.offer(new int[]{newDist, e.to});
            }
        }
    }
    return dist;
}

TypeScript 實作

// 用 adjacency list + Map 表示加權圖
type Graph = Map<string, Map<string, number>>;
 
function dijkstra(graph: Graph, source: string): Map<string, number> {
  const dist = new Map<string, number>();
  const visited = new Set<string>();
 
  // 初始化：所有距離設為 Infinity
  for (const node of graph.keys()) dist.set(node, Infinity);
  dist.set(source, 0);
 
  // 簡化版 priority queue（實務用 heap）
  while (visited.size < graph.size) {
    // 找未訪問中距離最小的節點
    let u = '';
    let minDist = Infinity;
    for (const [node, d] of dist) {
      if (!visited.has(node) && d < minDist) {
        u = node;
        minDist = d;
      }
    }
    if (u === '') break;
 
    visited.add(u);
 
    // 更新鄰居
    for (const [v, weight] of graph.get(u) ?? []) {
      const newDist = dist.get(u)! + weight;
      if (newDist < dist.get(v)!) {
        dist.set(v, newDist);
      }
    }
  }
  return dist;
}
 
// 使用：計算辦公室各站點之間的最短通勤距離
const metro: Graph = new Map([
  ['台北車站', new Map([['中山', 3], ['善導寺', 2]])],
  ['中山', new Map([['台北車站', 3], ['松江南京', 4]])],
  ['善導寺', new Map([['台北車站', 2], ['忠孝新生', 3]])],
  ['松江南京', new Map([['中山', 4], ['忠孝新生', 2]])],
  ['忠孝新生', new Map([['善導寺', 3], ['松江南京', 2]])],
]);
 
const distances = dijkstra(metro, '台北車站');
// 台北車站 → 忠孝新生: 5（經善導寺比經中山快）

特性

項目	說明
時間	O((V + E) log V)
限制	不能有負權重
適用	單源最短路徑

工程場景：網路路由協定 OSPF（Open Shortest Path First）就是用 Dijkstra 計算路由器之間的最短路徑。每台路由器會建立整個網路的拓撲圖，然後跑 Dijkstra 決定封包要怎麼走。

Bellman-Ford 演算法

可以處理負權重邊，也可以偵測負環。

原理

對所有邊做 V-1 次「鬆弛」：

鬆弛：如果經過 u 到 v 更短，就更新
if (dist[u] + weight < dist[v]) {
    dist[v] = dist[u] + weight;
}

偵測負環

第 V 次鬆弛還能更新 = 有負環（距離可以無限小）

// V-1 次鬆弛
for (int i = 0; i < V - 1; i++) {
    for (每條邊 (u, v, w)) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
        }
    }
}
 
// 第 V 次：檢測負環
for (每條邊 (u, v, w)) {
    if (dist[u] + w < dist[v]) {
        return "有負環！";
    }
}

特性

項目	說明
時間	O(V × E)
優點	可處理負權重
用途	偵測負環

工程場景：金融系統中的套利偵測。如果匯率圖中存在「負環」（A→B→C→A 換完錢反而更多），就表示有套利機會。交易所會用 Bellman-Ford 偵測這種情況。

Floyd-Warshall 演算法

求所有點對之間的最短路徑。

原理

DP：dist[i][j] = 從 i 到 j，允許經過節點 0~k 的最短路徑

dist[i][j] = min(
    dist[i][j],           // 不經過 k
    dist[i][k] + dist[k][j]  // 經過 k
)

實作

for (int k = 0; k < V; k++) {
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
}

特性

項目	說明
時間	O(V³)
空間	O(V²)
用途	所有點對最短路徑

拓撲排序

線性排列 DAG（有向無環圖）的節點。

用途：課程依賴、編譯順序、任務排程

課程依賴：
  微積分 → 線性代數 → 機器學習
  程式設計 → 資料結構 → 演算法

拓撲排序：微積分, 程式設計, 線性代數, 資料結構, 機器學習, 演算法

TypeScript 實作（Kahn’s Algorithm）

// 通用拓撲排序 — 適用於任何依賴關係場景
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);
    }
  }
 
  // 入度為 0 的先加入
  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;
}

工程實戰：npm 的套件安裝順序

npm install 背後就是拓撲排序。每個套件有自己的 dependencies，npm 要決定先安裝哪個：

// 模擬 npm 的套件安裝順序決策
const packages = new Map<string, string[]>([
  // package → 它的依賴
  ['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']
// → 先裝沒有依賴的，再裝依賴它們的

其他拓撲排序場景：Webpack/Vite 的 module bundling（決定 import 順序）、CI/CD pipeline 的 job 排程（build → test → deploy）、資料庫 migration 的執行順序。

Java 實作（Kahn’s Algorithm）

List<Integer> topoSort(Graph g) {
    int[] inDegree = new int[V];
 
    // 計算入度
    for (每條邊 (u, v)) {
        inDegree[v]++;
    }
 
    // 入度為 0 的先加入
    Queue<Integer> queue = new LinkedList<>();
    for (int i = 0; i < V; i++) {
        if (inDegree[i] == 0) queue.add(i);
    }
 
    List<Integer> result = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        result.add(u);
 
        for (v : neighbors(u)) {
            inDegree[v]--;
            if (inDegree[v] == 0) queue.add(v);
        }
    }
 
    return result;
}

A* 演算法

啟發式搜尋：比 Dijkstra 更聰明。

原理

f(n) = g(n) + h(n)

g(n) = 從起點到 n 的實際距離
h(n) = 從 n 到終點的估計距離（啟發函數）

啟發函數

函數	公式	適用
曼哈頓	|x1-x2| + |y1-y2|	網格（只能上下左右）
歐幾里得	√((x1-x2)² + (y1-y2)²)	任意方向
切比雪夫	max(|x1-x2|, |y1-y2|)	網格（含對角）

A* vs Dijkstra

        終點
          ↑
    □ □ □ □ □
    □ ■ ■ ■ □    ■ = 障礙物
    □ □ □ ■ □
    □ ■ □ □ □
    起點

Dijkstra：往所有方向擴展（藍色區域大）
A*：往終點方向擴展（藍色區域小）

比較	Dijkstra	A*
擴展方向	所有方向	往目標方向
速度	較慢	較快
最佳解	保證	保證（若 h 可接受）

工程場景：地圖導航

Google Maps 不是單純跑 Dijkstra，它用的是 A* 的變體。地圖資料本身就是一張巨大的加權圖（路口 = 節點、道路 = 邊、距離/時間 = 權重）。A* 利用「直線距離到終點」當啟發函數，避免向反方向搜尋，大幅減少搜尋範圍。

// 簡化版 A* — 網格地圖上的路徑搜尋
interface Point { x: number; y: number }
 
function manhattanDistance(a: Point, b: Point): number {
  return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}
 
function aStar(grid: number[][], start: Point, end: Point): Point[] {
  const rows = grid.length, cols = grid[0].length;
  const openSet = new Map<string, { point: Point; f: number; g: number; parent?: string }>();
  const closedSet = new Set<string>();
  const key = (p: Point) => `${p.x},${p.y}`;
 
  openSet.set(key(start), {
    point: start,
    g: 0,
    f: manhattanDistance(start, end),
  });
 
  while (openSet.size > 0) {
    // 找 f 值最小的節點
    let currentKey = '';
    let minF = Infinity;
    for (const [k, v] of openSet) {
      if (v.f < minF) { minF = v.f; currentKey = k; }
    }
 
    const current = openSet.get(currentKey)!;
    if (current.point.x === end.x && current.point.y === end.y) {
      // 回溯路徑
      return reconstructPath(currentKey, openSet);
    }
 
    openSet.delete(currentKey);
    closedSet.add(currentKey);
 
    // 探索四個方向的鄰居
    for (const [dx, dy] of [[0,1],[0,-1],[1,0],[-1,0]]) {
      const nx = current.point.x + dx, ny = current.point.y + dy;
      const nk = `${nx},${ny}`;
 
      if (nx < 0 || nx >= rows || ny < 0 || ny >= cols) continue;
      if (grid[nx][ny] === 1 || closedSet.has(nk)) continue; // 1 = 障礙物
 
      const g = current.g + 1;
      const f = g + manhattanDistance({ x: nx, y: ny }, end);
 
      const existing = openSet.get(nk);
      if (!existing || g < existing.g) {
        openSet.set(nk, { point: { x: nx, y: ny }, g, f, parent: currentKey });
      }
    }
  }
  return []; // 無路可走
}

延伸：實際導航系統會用更高階的演算法如 Contraction Hierarchies 或 ALT (A* + Landmarks + Triangle inequality) 做預處理，讓查詢從數秒降到毫秒等級。

演算法比較

演算法	時間	負權重	用途
Dijkstra	O((V+E) log V)	✗	單源最短路徑
Bellman-Ford	O(V × E)	✓	單源 + 負環偵測
Floyd-Warshall	O(V³)	✓	所有點對最短路徑
A*	O(E)	✗	點對點（有啟發函數）
拓撲排序	O(V + E)	-	DAG 排序

如何選擇？

需要最短路徑？
├─ 單源到所有點
│   ├─ 有負權重？→ Bellman-Ford
│   └─ 無負權重？→ Dijkstra
├─ 所有點對？→ Floyd-Warshall
└─ 點到點（地圖）？→ A*

---

工程實務：選擇正確的圖演算法

你想做什麼	用什麼	實際案例
計算兩點最短路徑	A*	地圖導航
計算一點到所有點的最短路徑	Dijkstra	網路路由（OSPF）
有負權重的最短路徑	Bellman-Ford	匯率套利偵測
所有點對之間的距離	Floyd-Warshall	小型網路的全對最短路徑
決定依賴/安裝順序	拓撲排序	npm install、CI/CD pipeline
偵測循環依賴	拓撲排序（檢查結果大小）	ESLint circular dependency
找社群/連通元件	BFS / DFS	社群網站推薦

什麼時候不需要圖演算法

• 資料沒有「關係」概念：純粹的列表、集合 → 用 Hash Table 或 Array
• 樹狀結構：有明確的父子關係、不需要處理環 → 用 Tree 的遍歷就好
• 只需排序：資料之間沒有依賴關係 → 用 排序演算法

---

延伸閱讀

• Tree 樹 — 圖的特例（無環連通圖）
• 動態規劃 — Floyd-Warshall 本質是 DP
• Hash Table — 圖的 adjacency list 通常用 hash map 實作
• 貪心演算法 — Dijkstra 是貪心策略的經典應用

相關檔案

• Java 實作：GraphAlgorithms.java
• 視覺化：graph-algorithms.html
• 圖基礎：Graph 筆記