图
邻接表
邻接表是存储图最常见的方式：对每一个顶点，都保存一份它直接相连的顶点清单。可以把它想成一本通讯录，每个人名下都有一小串自己能打通的号码。要找某个顶点的邻居，直接翻它那一行就行——不必搜遍整张图。
把它和另一种经典选择邻接矩阵比一比：邻接矩阵是一张 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）用邻接表，稠密图或需要瞬时查边时用邻接矩阵。
又称
另见