鄰接串列與鄰接矩陣（adjacency list vs adjacency matrix）

在執行任何圖演算法之前，你得先把圖記在某處，而自然的做法有兩種。想像一個 n 個人的小型社交網路。一種做法是用一個 n 乘 n 的大格子，第 u 列第 v 行的格子若 u 與 v 是朋友就填 1、否則填 0——這就是鄰接矩陣。另一種做法是給每個人一張小清單，只列出他確實有的朋友——這就是鄰接串列。兩者記錄的是同樣的友誼，差別只在於它們讓哪些操作變快、哪些變浪費。

精確地說：鄰接矩陣 A 是一個 n 乘 n 的陣列，當 u 到 v 有一條邊時 A[u][v] = 1（若是加權圖則填權重而非 1）。無論邊有多少，它都占用 Theta(n^2) 的空間，但只要一次查表就能在 O(1) 內回答「u 與 v 相鄰嗎？」。鄰接串列則為每個頂點 u 存一份其鄰居的清單；它占用 Theta(n + m) 的空間（m 為邊數），而掃過 u 的所有鄰居所花的時間正比於 u 的度數。這個取捨在圖搜尋最常用的兩個操作上最為鮮明：BFS 與 DFS 各拜訪每個頂點、各沿每條邊走一次，因此整趟下來串列讓它們在 O(n + m) 內完成，而矩陣卻迫使它們對每個頂點掃過一整列長度 n 的格子，即使在稀疏圖上也得花 O(n^2)。

該選哪一種，取決於稠密程度。當 m 遠小於 n^2 時圖是稀疏的（想想道路圖或社交圖，每個頂點只連到寥寥幾個其他頂點）；此時串列在空間與整趟走訪的時間上都大獲全勝。當 m 接近 n^2 時圖是稠密的，或當你不斷詢問單一邊是否存在、或做矩陣式的運算（例如把 A 取冪以計算路徑數）時，矩陣 O(1) 的查表與緊湊的 n^2 占用就划算了。多數真實世界的圖是稀疏的，這正是鄰接串列成為本領域幾乎每個演算法預設表示法的原因。