GESP 七级 · GESP 202412 C++ 七级 第 22 题

邻接表和邻接矩阵都是图的存储形式。邻接表在遍历单个顶点的所有边时，时间复杂度更低；邻接矩阵在判断两个顶点之间是否有边时，时间复杂度更低。

邻接矩阵是n×n的方阵，matrix[i][j]表示顶点i到j是否有边（有权图存权值）。n个顶点需n²空间。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】邻接表｜邻接矩阵｜图遍历时间复杂度

1. 考纲定位：GESP七级《数据结构》模块，命题人瞄准"存储结构适用场景混淆"这一高频失分点。多数考生误以为邻接表/矩阵各有绝对优劣，实则需结合具体操作判断。

2. 解题思维：遍历单顶点所有边时，邻接表直接沿链表遍历，时间复杂度O(顶点度数)；邻接矩阵需扫描整行，复杂度O(n)。判断两顶点是否相连，邻接矩阵查表O(1)，邻接表需遍历链表O(度数)。核心方法：先明确操作类型，再对比两种结构在该操作下的时间复杂度。

3. 陷阱拆解：选项B的陷阱在于"偷换操作"——考生易将"遍历边"误解为遍历整个图，或将"判断相连"误用空间复杂度衡量。最阴险处是"单个顶点"限定，若忽略此条件便可能误判矩阵优势。

4. 反命题思维：若改问"添加边"，答案变为B；若问"稀疏图存储"，则B成立。刷到同类题时，先问"操作是什么"，再对比两种结构在该操作下的复杂度。