CSP-S 提高级 · CSP 2019 提高级第一轮 第 12 题

以下哪个结构可以用来存储图（）

这题其实是在考你对数据结构的‘适用范围’有没有数清楚。拿到题先想：图是多对多关系，那谁能存多对多？栈、队列、二叉树都只能存线性或一对一/一对多，只有邻接矩阵是专门给图设计的，直接锁定D。

最容易把二叉树当成图的存储，因为二叉树也是树，而树是图的子集，但二叉树节点最多两个子节点，存不了多对多；其次是混淆‘矩阵’和‘邻接矩阵’，以为任何二维数组都能存图；还有人觉得栈队列能存图，其实它们只是线性容器，没法表达顶点的连接关系。

Q12 图的存储结构

考察知识点

• 图的存储方式
• 图的基本概念
• 常见图存储结构

概念定义

图的存储结构主要有两种： 1. 邻接矩阵（Adjacency Matrix）：$n \times n$ 矩阵，$matrix[i][j]$ 表示顶点 i 到 j 是否有边（或边的权值）。空间复杂度 $O(n^2)$。 2. 邻接表（Adjacency List）：为每个顶点维护一个链表/列表，存储与其相邻的顶点。空间复杂度 $O(n+m)$。

其他存储方式还有：边集数组、前向星等。

逐步推导

• A. 栈：一种线性数据结构，后进先出（LIFO），不能存储图 ❌
• B. 二叉树：一种层次树形结构，每个节点最多有两个子节点，只能表示"一对多"关系，不能表示图的"多对多"关系 ❌
• C. 队列：一种线性数据结构，先进先出（FIFO），不能存储图 ❌
• D. 邻接矩阵：专门的图存储结构 ✅

避坑指南

• 邻接矩阵 ≠ 矩阵存储：虽然都是矩阵，但邻接矩阵是专为图设计的
• 二叉树是树的一种，树是图的子集（无环连通图），但一般图无法用二叉树存储
• 栈和队列是容器（线性表），不是图的存储结构

技巧总结

• 选择存储结构的考量：稠密图用邻接矩阵，稀疏图用邻接表
• 有向图和无向图的邻接矩阵分别是对称/非对称
• 邻接矩阵适合快速判断两点间是否有边（O(1)），但空间大
• 邻接表适合遍历邻接点（边数相关），但不能O(1)判断边存在性

考频与趋势

图的存储结构在题库中共考过32题，覆盖5个考试级别（2009-2025）。历年分布：2009年1题、2014年1题、2015年1题、2016年1题、2017年1题、2019年1题、2020年1题、2022年1题、2023年4题、2024年10题、2025年10题。分赛事：GESP 七级13题、GESP 八级11题、NOIP 提高组 初赛5题、CSP 提高级2题、CSP 入门级1题。

预测

从数据看，2023-2025年该考点密集出现（共24题），且GESP七、八级占比最高。预计未来两三年内仍会高频考查，形式可能更灵活，比如结合邻接表与邻接矩阵的对比，或给出具体图结构问空间复杂度。暂无足够依据预测具体年份或题型变化。