2.2 邻接表

文档摘要

2.2 邻接表图论基础：概念、算法与应用背景二、图的表示方法 2.2 邻接表：化繁为简，高效存储图结构在图论的世界里，图的表示方法至关重要，它直接影响着算法的效率和内存的使用。上一节我们已经领略了邻接矩阵的风采，它以直观的方式展示了图中节点之间的连接关系。然而，当面对稀疏图（节点多，边少）时，邻接矩阵会显得有些“笨重”，浪费大量的存储空间。这时，邻接表便闪亮登场，以其精巧的设计，成为了表示稀疏图的理想选择。 1. 邻接表的概念：化零为整，按需存储邻接表是一种链式存储结构，它为图中的每一个节点都维护一个列表，这个列表记录了与该节点相邻的所有节点。可以形象地理解为，每个节点都拥有一个“朋友列表”，记录了它所连接的所有“朋友”。