1006 字
3 分钟
考研专业课学习记录2026-07-07
考研专业课学习记录 | 2026-07-07
今日学习内容
今日共学习2.5小时，完成了深度优先搜索(DFS)、广度优先搜索(BFS)的代码背诵，同时学习并梳理了迪杰斯特拉算法、弗洛伊德算法以及最小生成树的核心考点与实现逻辑。
AI知识点带复盘
1. 图遍历算法（DFS & BFS）
属于408数据结构图章节核心基础考点：
- 实现方式：支持邻接表、邻接矩阵两种存储结构，DFS非递归版本借助栈模拟递归调用栈，BFS依赖队列实现层序遍历；
- 时间复杂度：邻接表实现为，邻接矩阵实现为；
- 核心应用：连通分量求解、拓扑排序、环检测、两点间路径查找等，是所有图算法的学习基础。
2. 迪杰斯特拉(Dijkstra)算法
单源最短路径经典贪心算法：
- 适用场景：非负权值的有向/无向图，求解从指定起点到其余所有顶点的最短路径；
- 核心步骤：初始化距离数组，每次选取未访问的距离起点最近的顶点，更新其邻接点的距离值，重复流程直至所有顶点完成访问；
- 优化考点：堆优化版本将时间复杂度从基础版的降至，是考研选择题与编程题高频考点；
- 注意事项：无法处理存在负权边的图。
3. 弗洛伊德(Floyd)算法
多源最短路径动态规划算法：
- 核心思想：通过动态规划转移方程
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])枚举中间顶点，逐步更新任意两点间的最短路径； - 实现方式：基于邻接矩阵存储，时间复杂度为，空间复杂度为；
- 适用场景：可处理存在负权边但不含负环的图，适合批量求解任意两点间的最短路径。
4. 最小生成树(MST)
图的经典优化问题，考研核心考点包含两种主流算法：
- Prim算法：以顶点为核心，每次选取连接当前生成树与外部顶点的最小权边扩展生成树，邻接矩阵实现复杂度适合稠密图，堆优化版本适配稀疏图；
- Kruskal算法：以边为核心，将所有边按权值升序排序，依次选取不形成环的边加入生成树，借助并查集实现环的快速判断，复杂度适合稀疏图；
- 核心考点：两种算法的贪心正确性证明、适用场景以及代码实现细节。
问题与反思
- 堆优化版迪杰斯特拉算法的代码实现细节还不够熟练，手写时容易在堆的更新和顶点访问标记上出错；
- 弗洛伊德算法的动态规划转移方程的推导逻辑还需要进一步梳理，对中间顶点的枚举顺序理解不够透彻；
- 最小生成树两种算法在处理不连通图时的边界情况处理还需要巩固。
收获与总结
- 熟练掌握了DFS、BFS的递归与非递归代码实现，理清了两种遍历算法的适用场景与差异；
- 清晰区分了单源最短路径（迪杰斯特拉）与多源最短路径（弗洛伊德）的算法逻辑、适用范围；
- 明确了最小生成树两种经典算法的核心区别与选择依据，能够独立完成两种算法的手写实现与复杂度分析。
💡 碎碎念：踏实吃透每一个知识点！
文档内容由 AI 辅助生成
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
考研专业课学习记录2026-07-07
https://elysiaweb.vercel.app/posts/408/7-7/ 部分信息可能已经过时
相关文章 智能推荐