🏷️ 知识点：邻接表空间复杂度

用邻接表法存储图所用的空间大小()。

A. 与图的顶点数和边数有关 B. 只与图的边数有关 C. 只与图的顶点数有关 D. 与边数的平方有关

[tag_link]

正确答案：A

结论

答案为 A：邻接表空间与顶点数和边数都有关。

推导

顶点表需要 (O(n))；有向图边结点为 (e)，无向图每条边存两次为 (2e)，总空间为 (O(n+e))。

易错点

不能只按边数估算，顶点表即使没有边也要占用空间。