图的存储结构：邻接矩阵与邻接表

"本书深入浅出地介绍了C++实现的数据结构和算法，涵盖了邻接矩阵等图的存储结构。" 在计算机科学中，图是一种重要的数据结构，用于表示对象之间的关系。图的存储结构对其算法设计和应用效率至关重要。本文主要讨论了两种常见的图存储方式：邻接矩阵和邻接表。 3.2.1 邻接矩阵存储结构 邻接矩阵是图的直观且直接的存储方法，尤其适用于稠密图（即图中边的数量接近于所有可能边的数量）。对于一个具有n个顶点的图，邻接矩阵是一个n×n的二维数组E，其中E[i][j]的值表示顶点i和顶点j之间是否存在边。如果存在边，E[i][j]通常赋值为1；若不存在边，赋值为0。这种表示方式使得查询任意两个顶点间是否有边的时间复杂度为O(1)，但占用的空间较多，不适合存储稀疏图（边的数量远小于所有可能边的数量）。 在邻接矩阵中，我们通常会同时维护一个Vertex数组，存储顶点的信息。例如，给定的图示例中，Vertex=(A,B,C,D,E)，而邻接矩阵E表示各个顶点之间的连接关系。 3.2.2 邻接表存储结构 相对于邻接矩阵，邻接表更适合存储稀疏图，它通过链表或数组的数组来表示图中各个顶点的邻接顶点。每个顶点对应一个链表（或数组），链表中存储的是与其相连的所有顶点的指针。这样，邻接表可以节省大量空间，特别是当图中边的数量较少时。然而，查询两个顶点间是否存在边的时间复杂度不再是O(1)，而是O(min{d_i, d_j})，其中d_i和d_j分别是顶点i和顶点j的度（即与它们相连的边的数量）。 《妙趣横生的算法（C++语言实现）》一书详细介绍了这些概念，并结合C++编程环境，通过精选例题帮助读者理解算法的实现和应用。书中不仅涵盖了基础的数据结构和算法，还包括高级图算法如拓扑排序和最小生成树等，旨在帮助读者从理论到实践全面掌握算法知识。此外，该书还提供了配套的教学视频，以辅助学习，特别适合算法初学者和有一定C++基础的读者，也可作为相关院校的教材或面试准备参考书。