圖
鄰接表
鄰接表是儲存圖最常見的方式：對每一個頂點，都保存一份它直接相連的頂點清單。可以把它想成一本通訊錄，每個人名下都有一小串自己能打通的號碼。要找某個頂點的鄰居，直接翻它那一行就行——不必搜遍整張圖。
把它和另一種經典選擇鄰接矩陣比一比：鄰接矩陣是一張 V×V 的方格表，若從 i 到 j 有邊，格子 [i][j] 就是 1，否則是 0。矩陣讓「i 與 j 之間是否有邊？」這個問題瞬間可答，但無論圖多稀疏（邊很少），它都恆佔 O(V^2) 的空間。鄰接表只佔 O(V + E) 的空間——每個頂點一格，每條邊一項——對於現實中最常見的稀疏圖（地圖、社群網路）來說要小得多。它的代價是：要判斷某一條具體的邊，得掃一遍那個頂點的清單。
由於廣度優先和深度優先這類走訪會造訪每個頂點、並沿每條邊走一遍，正是鄰接表 O(V + E) 的佈局讓這些演算法能跑出 O(V + E) 的時間。這也是大多數演算法程式碼預設採用它的原因。
vector<vector<int>> adj(3); // 3 vertices
adj[0] = {1, 2};
adj[1] = {0, 2};
adj[2] = {0, 1};
// neighbors of vertex 0:
for (int nb : adj[0]) { /* visit nb */ }adj[v] 保存從 v 直接可達的每個頂點。無向圖時兩個方向都要加。
經驗法則：稀疏圖（E 遠小於 V^2）用鄰接表，稠密圖或需要瞬時查邊時用鄰接矩陣。
又稱
另見