732 字
2 分钟
考研专业课学习记录2026-07-05
考研专业课学习记录 | 2026-07-05
今日学习内容
四十分钟，复习图的存储结构相关知识点，重点梳理了邻接存储、十字链表、邻接表的核心内容。
AI知识点带复盘
1. 邻接存储体系
邻接存储是图最常用的存储大类，包含邻接矩阵和邻接表两种基础形式：
- 邻接矩阵：通过二维数组
G[n][n]存储顶点间的边/弧关系，G[i][j] = 1（或对应权值）表示顶点到存在边。适用于稠密图，空间复杂度为，优点是可以快速判断两点间是否存在边，无向图的邻接矩阵是对称矩阵，考研常考察邻接矩阵的初始化、遍历适配性以及空间复杂度计算。 - 邻接表：链式存储结构，为每个顶点创建一个单链表存储其所有邻接点。适用于稀疏图，空间复杂度为（为顶点数，为边数）。无向图中每条边会被存储两次，有向图的邻接表仅能直接统计出度，若需统计入度需要额外构建逆邻接表。考研常考察邻接表的构建流程、与邻接矩阵的优劣对比，以及如何通过邻接表计算顶点的度。
2. 十字链表
十字链表是专门针对有向图优化的存储结构，结合了邻接表和逆邻接表的优点：
- 每个顶点包含两个指针域：分别指向以该顶点为弧尾的出边链表、以该顶点为弧头的入边链表；每个边结点包含弧尾、弧头顶点下标，以及指向同弧尾/弧头的下一条边的指针。
- 可以同时快速访问顶点的出度和入度，适配拓扑排序、关键路径等需要同时遍历出入边的算法场景。考研常考察十字链表的结点结构、与邻接表的区别以及适用场景。
问题与反思
今日学习时长较短，仅完成基础知识点梳理，未结合考研真题进行针对性练习，对十字链表的边结点结构细节记忆不够清晰，后续需要补充对应题型训练。
收获与总结
梳理了图的三类核心存储结构的适用场景与优缺点，明确了邻接矩阵、邻接表、十字链表分别适配的图类型与算法需求，理清了邻接存储体系下不同结构的核心差异。
💡 碎碎念：踏实吃透每一个知识点！
文档内容由 AI 辅助生成
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
考研专业课学习记录2026-07-05
https://elysiaweb.vercel.app/posts/408/7-5/ 部分信息可能已经过时
相关文章 智能推荐