邻接表：图的高效存储方式，比邻接矩阵好在哪？
这篇文章介绍了图的基本概念及两种核心存储方式：邻接矩阵与邻接表。图由顶点（如社交网络用户）和边（如好友关系）构成。 邻接矩阵是二维数组，用0/1表示顶点间是否有边，空间需n²（n为顶点数），查找边时间O(1)，但稀疏图（边少）时空间浪费大。邻接表则为每个顶点维护邻居列表（如用户好友列表），空间n+e（e为边数），仅存实际边，查找需遍历邻居表（时间O(degree(i))，i为顶点），遍历邻居更高效。 对比显示，邻接表在稀疏图（多数实际场景）中空间和时间效率均优于邻接矩阵，是处理图问题（如最短路径）的主流存储方式，更省空间且遍历更快。
阅读全文邻接矩阵：图的另一种表示方法，优缺点对比
邻接矩阵是图的一种基础表示方式，本质为n×n二维数组，行与列对应图的顶点，元素值表示顶点间边的存在性或权重。无向图中，元素1表示有边，0表示无边；有权图则直接存储权重值。 其优点：一是判断边存在仅需O(1)时间，计算顶点度高效（无向图行和，有向图行/列分别对应出/入度）；二是适合稠密图（边数接近n²），空间利用率高，且实现简单，便于初学者理解。 缺点：空间复杂度为O(n²)，稀疏图时浪费大量空间；遍历邻接顶点需O(n)时间，效率低于邻接表；动态调整边数灵活性不足。 总结：邻接矩阵以空间换时间，适合稠密图、需频繁查询边或计算度的场景，不适合稀疏图或需频繁遍历邻接顶点的场景，是理解图结构的基础工具。
阅读全文