邻接矩阵适用于密度＞15%的图，邻接表适用于稀疏图；判断依据是密度=2×边数/(顶点数×(顶点数−1))，结合空间效率与操作需求量化选择。

选邻接矩阵还是邻接表，关键看图的密度、操作类型和资源约束，不是凭感觉，而是有可量化的判断依据。

看图密度：用数字说话

密度 = 2×边数 / (顶点数 × (顶点数 − 1))（无向图）。这个值直接决定空间效率拐点：

• 密度 > 15% → 邻接矩阵更省空间（例如：1000个顶点、7.5万条边的交通路网）
• 密度
• 介于5%–15%之间时，需结合后续操作权衡，不能单看密度

看核心操作：查边、遍历、改结构谁更重要

不同操作在两种结构上性能差异显著：

• 查任意两点是否连通：邻接矩阵是 O(1)，邻接表需遍历链表，平均 O(度数)
• 遍历所有邻接点（如BFS/DFS）：邻接表是 O(V + E)，邻接矩阵是 O(V²)，稀疏图下差距可达百倍
• 增删边：两者都接近 O(1)；但删顶点时，邻接矩阵要移动整行整列，O(V²)，邻接表只需清空对应链表+更新其他节点指针，O(E)

看工程现实：内存、缓存、扩展性

真实系统里，理论复杂度之外还有硬约束：

• 1万个顶点的完全图：邻接矩阵占约400MB（int型），邻接表反而超1.2GB（因链表指针开销叠加）
• 百万级顶点的稀疏图：邻接矩阵内存直接溢出（需1PB级），邻接表可分片加载、支持外存或图数据库对接
• CPU缓存友好性：邻接矩阵是连续内存，遍历时局部性好；邻接表节点分散，易引发缓存未命中

典型场景速查建议

不必从头推导，按项目特征快速匹配：

• 路由协议、电路设计、小规模稠密图（
• 社交关系、知识图谱、推荐系统、大规模网络分析 → 选邻接表（常配合哈希表或动态数组优化）
• 需要频繁做矩阵运算（如路径计数、PageRank迭代）→ 邻接矩阵天然适配
• 图结构持续增长且边增删频繁 → 邻接表扩展更自然，避免反复重分配大块内存