跳到主要內容
Jasonmel Online

資料結構

資料怎麼排，決定了哪些操作便宜

主題 · 圖的表示法

圖的表示法

點和連線：用相鄰串列還是相鄰矩陣存，決定了「找鄰居」和「兩點有沒有連」哪個便宜，也決定了要多少記憶體。

圖
問題
u
ABCDEFGH
相鄰串列
  1. ABC
  2. BAD
  3. CADH
  4. DBCFG
  5. EGH
  6. FD
  7. GDE
  8. HCE
相鄰矩陣（第 u 列第 v 行是 1 表示 u→v 有邊）
ABCDEFGH
A01100000
B10010000
C10010001
D01100110
E00000011
F00010000
G00011000
H00101000
讀了但不是讀到答案鄰居

D 的鄰居是 B、C、F、G。相鄰串列直接讀 D 那一列的 4 個項目；矩陣得把整列 8 格都看過，因為它不知道哪幾格是 1。

串列這次讀了
4
矩陣這次讀了
8
串列佔的格子
26
矩陣佔的格子
64
亮起來的是這一步執行的程式碼
class Graph {
  adj: number[][];
  matrix: boolean[][];
 
  constructor(n: number, private directed: boolean) {
    this.adj = Array.from({ length: n }, () => []);
    this.matrix = Array.from({ length: n }, () =>
      new Array(n).fill(false));
  }
 
  addEdge(u: number, v: number): void {
    this.adj[u].push(v);
    this.matrix[u][v] = true;
    if (!this.directed) {
      this.adj[v].push(u);
      this.matrix[v][u] = true;
    }
  }
 
  neighboursFromList(u: number): number[] {
    return [...this.adj[u]];
  }
 
  neighboursFromMatrix(u: number): number[] {
    const found: number[] = [];
    for (let v = 0; v < this.matrix.length; v++) {
      if (this.matrix[u][v]) found.push(v);
    }
    return found;
  }
 
  hasEdgeInList(u: number, v: number): boolean {
    for (const w of this.adj[u]) {
      if (w === v) return true;
    }
    return false;
  }
 
  hasEdgeInMatrix(u: number, v: number): boolean {
    return this.matrix[u][v];
  }
}

模型假設與範圍

  • Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

什麼時候用

  • 大部分真實的圖都很稀疏（道路、社群、網頁、相依套件）：用相鄰串列，記憶體和點數加邊數成正比。
  • 圖很小或很稠密，而且常常要問「這兩點有沒有連」：用相鄰矩陣，一格就知道答案。
  • 要做矩陣運算的場合（例如算 k 步之內能到哪、PageRank 的冪迭代）也自然用矩陣。

和其他主題的關係

由這些組成
動態陣列
延伸閱讀
並查集

語言內建的版本

Map<number, number[]>

沒有內建的圖型別。慣用寫法是鄰接串列：一個 Map，從節點對到它的鄰居陣列。

操作寫法成本
加一條邊adj.get(u)!.push(v)O(1) amortised
某點的鄰居adj.get(9) ?? []O(1)
BFS 取出下一個queue[head]O(1)
BFS 走完整張圖bfs(0)O(V + E)
const edges = [[0, 1], [0, 2], [1, 3], [2, 3]];
const adj = new Map<number, number[]>();
for (const [u, v] of edges) {
  if (!adj.has(u)) adj.set(u, []);
  if (!adj.has(v)) adj.set(v, []);
  adj.get(u)!.push(v);
  adj.get(v)!.push(u);
}
adj.get(3);                        // → [1, 2]
adj.get(9);                        // → undefined
adj.get(9) ?? [];                  // → []
 
// BFS (Breadth-First Search): an index into the array instead of shift().
function bfs(start: number): Map<number, number> {
  const dist = new Map([[start, 0]]);
  const queue = [start];
  for (let head = 0; head < queue.length; head++) {
    const u = queue[head];
    for (const v of adj.get(u) ?? []) {
      if (!dist.has(v)) {
        dist.set(v, dist.get(u)! + 1);
        queue.push(v);
      }
    }
  }
  return dist;
}
[...bfs(0)];                       // → [[0, 0], [1, 1], [2, 1], [3, 2]]

每個 → 後面的結果都是實際執行這段程式碼驗證過的。

  • 無向圖的每條邊要加兩次（u→v 和 v→u），漏掉一邊就會變成有向圖，BFS 會少走到一些點。
  • BFS（Breadth-First Search，廣度優先搜尋）的佇列不要用 shift()：它是 O(n)，整個 BFS 會變成 O(V²)。用一個 head 索引往前走就好。
  • 節點是 0 到 n−1 的整數時，number[][]（Array.from({ length: n }, () => [])）比 Map 更快也更省。

時間與空間複雜度（Big O）

操作平均最差
列出 u 的鄰居（串列）
deg u 是 u 的鄰居數
O(deg u)O(V)
列出 u 的鄰居（矩陣）O(V)O(V)
u、v 有沒有邊（串列）O(deg u)O(V)
u、v 有沒有邊（矩陣）O(1)O(1)
加一條邊
兩種都是
O(1)O(1)

空間：O(V + E) / O(V²)，前者是相鄰串列，後者是相鄰矩陣

Big O 實測：n 變大時步數怎麼長

數的是：格子數或讀取次數（隨機稀疏圖，每點平均約 4 個鄰居；n 是點數）

Big On = 100n = 1,000n = 10,000成長倍數：實測（理論）
記憶體：相鄰串列O(n)4784,99249,988×105 (×100)
記憶體：相鄰矩陣O(n²)10,0001,000,000100,000,000×10,000 (×10,000)
列出鄰居：相鄰串列O(1)3.84.03.9×1.0 (×1.0)
列出鄰居：相鄰矩陣O(n)1001,00010,000×100 (×100)

點數變成一百倍：矩陣的記憶體變成一萬倍，串列只變一百倍；而串列列出鄰居的成本根本不動，因為每個點的鄰居數沒變。矩陣在 n = 10,000 時並沒有真的配置，而是照樣一格一格讀過整列來計數。

和其他做法比

邊數記憶體：串列／矩陣列出鄰居：串列／矩陣檢查一條邊：串列／矩陣
稀疏（每點平均 4.0 個鄰居）1,9964,992 / 1,000,0004.1 / 1,0004.1 / 1
稠密（每點平均 498.8 個鄰居）249,415499,830 / 1,000,000498.7 / 1,000367.1 / 1

兩張隨機圖都是 1,000 個點；稀疏的每點隨機連兩條，稠密的每一對點有一半機率相連。操作數是隨機挑 1,000 個點或點對的平均讀取次數。稀疏圖用矩陣，九成九以上的格子都是 0，白白佔記憶體；稠密圖時兩者記憶體差不多，矩陣檢查一條邊卻只要一格。

真實世界裡的它

  • 地圖導航的路網、社群網站的追蹤關係、套件管理器的相依關係，存的都是相鄰串列。
  • 大型稀疏圖常用 CSR（Compressed Sparse Row）格式：把所有鄰居串成一個大陣列，再用一個陣列記每個點從哪裡開始，對 CPU 快取更友善。
  • BFS（Breadth-First Search，廣度優先搜尋）、DFS（Depth-First Search，深度優先搜尋）、最短路徑、拓撲排序都是在相鄰串列上一個一個看鄰居。

取捨與陷阱

  • 矩陣的記憶體是 V²：一百萬個點就是一兆格，就算每格只用一個位元也要 125 GB。
  • 無向圖的每條邊在相鄰串列裡要存兩次（u 的串列一次、v 的串列一次），刪邊時兩邊都要刪。
  • 相鄰串列裡檢查一條邊要掃整個鄰居串列；如果這種查詢很多，可以把每個點的鄰居改存成雜湊集合。

LeetCode 練習