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

邻接表和邻接矩阵都是图的存储形式。通常，使用邻接表比使用邻接矩阵的时间复杂度更低。

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

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

【考点】图存储结构｜空间复杂度｜时间复杂度

考纲定位：本题在 GESP 七级“数据结构与算法”模块，核心考查图存储结构的空间复杂度与时间复杂度对比。命题人刻意将“邻接表”和“邻接矩阵”并列，实则是想抓住考生对“时间复杂度”理解的片面性——只知邻接表省空间，却忽略矩阵在特定操作（如边存在性查询）下的 O(1) 优势。

解题思维：看到“通常”二字，先拆解为两个子命题：① 邻接表比邻接矩阵省空间（真）；② 邻接表比邻接矩阵快（假）。关键观察是时间复杂度与操作类型密切相关：遍历所有边时，邻接表 O(V+E)，矩阵 O(V²)，稀疏图确实前者优；但查询某条边是否存在，矩阵 O(1)，邻接表需 O(1) 哈希或 O(deg(v)) 线性扫描，稠密图时矩阵更快。因此“通常”不成立。

陷阱拆解：A 选项的“正确”是命题人利用的绝对化表述陷阱——学生背诵“邻接表适合稀疏图”结论，却未意识到“适合”是相对于遍历操作，而非所有操作。B 选项的“错误”正是要求考生识别出“通常”一词的误导性。若只背“邻接表更优”而不分场景，就会掉进这个坑。

反命题思维：若把“通常”改为“在遍历所有边且图稀疏时”，则命题变为真；若把“邻接表”改为“邻接矩阵”，则命题变为“矩阵在查询边存在性时更优”，答案也会反转。提醒：刷到类似题，先问“命题人想考我什么场景？”