邻接表：图的高效存储方式，比邻接矩阵好在哪？

这篇文章介绍了图的基本概念及两种核心存储方式：邻接矩阵与邻接表。图由顶点（如社交网络用户）和边（如好友关系）构成。 邻接矩阵是二维数组，用0/1表示顶点间是否有边，空间需n²（n为顶点数），查找边时间O(1)，但稀疏图（边少）时空间浪费大。邻接表则为每个顶点维护邻居列表（如用户好友列表），空间n+e（e为边数），仅存实际边，查找需遍历邻居表（时间O(degree(i))，i为顶点），遍历邻居更高效。 对比显示，邻接表在稀疏图（多数实际场景）中空间和时间效率均优于邻接矩阵，是处理图问题（如最短路径）的主流存储方式，更省空间且遍历更快。