图论学习阶段性总结
· 阅读需 3 分钟
本站仅供本人学习使用。本文是我在 2026 年 3 月完成图论基础模块后的复盘与沉淀。
🎯 为什么学图论？
- 高频考点：图相关问题在大厂面试中频繁出现（如最短路径、连通性、最小生成树等）。
- 建模能力：现实世界中的网络、依赖关系、路径规划等问题天然适合用图建模。
- 算法基石：掌握图的遍历与经典算法，是理解更复杂数据结构（如网络流、拓扑排序）的前提。
📚 已掌握的核心内容
| 模块 | 关键知识点 | 典型算法/工具 |
|---|---|---|
| 基础概念 | 有向图 vs 无向图、度（入度/出度）、连通性（强连通分量） | — |
| 图的表示 | 邻接矩阵（稠密图）、邻接表（稀疏图） | — |
| 遍历策略 | 深度优先搜索（DFS）、广度优先搜索（BFS） | 栈/递归、队列 |
| 集合管理 | 不相交集合的合并与查询 | 并查集（路径压缩 + 按秩合并） |
| 最小生成树 | 连接所有节点的最小权重子图 | Prim（点贪心）、Kruskal（边贪心 + 并查集） |
| 最短路径 | 单源最短路径问题 | Dijkstra（非负权）、Bellman-Ford（含负权） |
💡 刷题实践与典型题型
通过 KamaCoder 和 LeetCode 完成以下类型题目：
1. DFS/BFS 应用
- 所有可达路径：回溯记录完整路径（DFS 模板）。
- 岛屿问题系列（计数、最大面积、沉没孤岛）：网格 DFS + 反向思维（“灌水法”）。
- 高山流水：双起点反向 DFS，求交集区域。
2. 并查集实战
- 寻找存在的路线：判断两点是否连通（基础 Union-Find）。
- 多余的边：检测环的形成（Kruskal 的逆向应用）。
- 建造最大岛屿：预处理岛屿编号 + 枚举填海（两阶段优化）。
3. 最小生成树（MST）
- 寻宝 / 连接所有点的最小费用：Prim（邻接矩阵）与 Kruskal（边排序 + 并查集）双解法对比。
- 非连通图处理：Kruskal 中检查
used_edge == n-1。
4. 最短路径
- 参加科学大会：Dijkstra 求单源最短路（优先队列优化）。
- 城市间货物运输：Bellman-Ford 处理负权边，并检测负环影响。
🔧 工具与方法论
- 刷题平台：LeetCode、KamaCoder
- 学习参考：代码随想录 - 图论精讲
- 代码规范：
- C++ ACM 模式（主函数读写 + 算法封装）
- 模板化实现（如
UnionFind,dijkstra,kruskal） - 边界条件全覆盖（图不连通、全陆地、负环等）
🔄 下一步计划
- 进阶图算法：拓扑排序、欧拉路径、二分图匹配。
- 动态规划 + 图结合：如 DAG 上的 DP。
- 真题强化：LeetCode Hot 100 图论专题 + 周赛真题复现。
💬 最后
图论不是一蹴而就的技能，而是日积月累的沉淀。
从死记模板到理解“为什么用这个算法”，每一道题都是思维的锤炼。
我会在这里持续更新我的思考、错误、优化与总结。不为炫耀，只为成长。
🌐 在线访问：https://algo.zj.cn
📝 备案号：鄂ICP备2026007433号