图的表示方式

邻接矩阵 vs 邻接表 — 两种存储图的方式

---

概念

对比

特性	邻接矩阵	邻接表
空间	O(V²)	O(V + E)
查边	O(1)	O(度数)
遍历邻居	O(V)	O(度数)
加边	O(1)	O(1)
适合	稠密图	稀疏图

何时用哪个

图类型	顶点数	边数	最佳表示
稠密图	100	~4,950	矩阵
稀疏图	1,000	~5,000	表
社交网络	1M	~10M	表（极稀疏）

---

决策指南

场景	推荐
稠密图	邻接矩阵
稀疏图	邻接表
需要快速查边	矩阵
内存受限	表
需要遍历邻居	表（只遍历存在的边）