1655 字
4 分钟
考研专业课学习记录2026-06-10
考研专业课学习记录 | 2026-06-10
今日学习内容
今日累计学习2.5小时，主要复习了数据结构图模块核心知识点，包括：图的两种基础存储结构（邻接矩阵、邻接表）、图的两种遍历方式（DFS深度优先搜索、BFS广度优先搜索，修正笔误：原记录的DBS为BFS）、最小生成树相关算法（Prim普利姆算法、Kruskal克鲁斯卡尔算法，修正笔误：原记录的卡酷斯特为克鲁斯卡尔）、单源最短路径算法（Dijkstra迪杰斯特拉算法），以及任务调度相关的AOV网与AOE网知识点。
AI知识点带复盘
1. 图的基础存储结构
邻接矩阵
- 实现逻辑：通过二维数组
G[n][n]存储图的边关系与权值，无向图满足G[i][j]=G[j][i]，无权图用1/0标记是否存在边，带权图直接存储边权值。 - 复杂度与场景：空间复杂度
O(n²)，适合稠密图，查询顶点i的邻接点时间复杂度为O(n)，408常考察其空间浪费问题与稠密图适配性。
邻接表
- 实现逻辑：为每个顶点维护一个单链表，存储其所有邻接点与对应边权，带权图的链表节点需额外存储权值信息。
- 复杂度与场景：空间复杂度
O(n+e)（e为总边数），适合稀疏图，查询顶点i的邻接点时间复杂度为顶点i的出边数，408常考察其空间优化特性与稀疏图适配性。
2. 图的遍历算法
DFS深度优先搜索
- 核心逻辑：沿着单条路径尽可能深地遍历，无法继续时回溯，递归实现依赖系统栈，非递归实现需手动模拟栈结构。
- 复杂度与应用：邻接表实现时间复杂度
O(n+e)，邻接矩阵实现O(n²)，可用于求解连通分量、判断图的连通性，是拓扑排序的前置基础。
BFS广度优先搜索
- 核心逻辑：按层级遍历图，借助队列实现节点访问顺序，可直接求解无权图的单源最短路径。
- 复杂度与应用：复杂度同DFS，常考察遍历序列生成、分层图问题求解，以及有向图强连通分量的求解思路。
3. 最小生成树（MST）
Prim算法
- 核心逻辑：从单个起始顶点出发，每次选择连接当前生成树与外部顶点的最小权值边，将对应顶点加入生成树，重复执行
n-1次得到最小生成树。 - 实现与场景：邻接矩阵版本时间复杂度
O(n²)，适配稠密图；堆优化邻接表版本复杂度O(elogn)，适配稀疏图。
Kruskal算法
- 核心逻辑：将所有边按权值从小到大排序，依次选取边，若边的两个顶点不在同一连通分量中，则将其加入生成树，直到包含
n-1条边。 - 实现与场景：借助并查集维护连通分量，时间复杂度
O(eloge)，适配稀疏图，408常考察其并查集的使用细节。
4. 单源最短路径：Dijkstra算法
- 核心逻辑：贪心算法，每次选取当前距离源点最近的未访问顶点，更新其邻接点的最短距离，不支持负权边与负环。
- 实现步骤：初始化距离数组，源点距离设为0，其余顶点设为无穷大；循环
n次，每次选取未访问的最小距离顶点，标记已访问后更新邻接点距离。 - 复杂度与考点：邻接矩阵版本
O(n²)，堆优化版本O(elogn)，408常考察初始化边界、不可达顶点的处理逻辑。
5. AOV与AOE任务调度网
AOV网（顶点表示活动）
- 核心逻辑：通过拓扑排序判断有向图是否存在环，拓扑序列即为活动的可行执行顺序，解决任务先后依赖问题。
- 考点：拓扑排序的实现步骤、有向无环图的环判断。
AOE网（边表示活动）
- 核心逻辑：求解项目的关键路径，即从源点到汇点的最长路径，关键活动为总时差为0的边，直接决定项目最短工期。
- 核心计算：需正向遍历计算活动最早开始时间、反向遍历计算活动最晚开始时间，通过
最晚开始时间-最早开始时间得到总时差，408常考察完整关键路径计算流程。
问题与反思
- 曾混淆Prim与Kruskal算法的适用场景，对两种算法的适配图类型记忆不够牢固；
- Dijkstra算法的初始化细节容易出错，比如忘记将非源点顶点的初始距离设为无穷大，或标记已访问顶点的时机有误；
- AOE网的关键路径计算中，容易搞混最早/最晚开始时间的遍历顺序，导致计算结果偏差；
- 手写邻接表与邻接矩阵的转换代码时，常出现下标越界的问题；
- 初期曾将BFS误写为DBS，对算法名称的记忆不够精准。
收获与总结
- 系统梳理了408数据结构图模块的全部核心考点，明确了每种存储结构、遍历算法、优化算法的适用场景与复杂度；
- 修正了前期的笔误，强化了Kruskal、BFS等标准算法名称的正确记忆；
- 清晰区分了AOV与AOE网的核心差异，能够独立完成关键路径的完整计算流程；
- 掌握了图遍历、最小生成树、最短路径的核心代码框架，能够快速写出考试要求的核心逻辑；
- 明确了该模块在408考试中的常见题型：选择题侧重算法场景判断、综合题侧重算法实现与路径计算。
💡 碎碎念：踏实吃透每一个知识点！
文档内容由 AI 辅助生成
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
考研专业课学习记录2026-06-10
https://elysiaweb.vercel.app/posts/408/6-10/ 部分信息可能已经过时
相关文章 智能推荐