图论学习路线

专题特点

图论专题采用 ACM 输入输出模式，覆盖 DFS、BFS、并查集、最小生成树、拓扑排序与最短路算法。

核心方法

先识别图的方向、权值与连通性，再选择遍历或路径算法。

如何学习

先把邻接矩阵和邻接表的建图写熟，再分别掌握 DFS 和 BFS。进入最短路前，先判断边权是否为负、是单源还是多源，再选择算法。

建议按照下面的顺序学习。第一遍先理解思路并独立写出代码，第二遍再对照题解复盘边界条件和复杂度。

学习顺序

• 图论正式发布
• 本章为什么用ACM模式
• 图论理论基础
• 深度优先搜索理论基础
• 可达路径
• 广度优先搜索理论基础.md
• 岛屿问题（一）孤岛计数.深搜版
• 岛屿问题（二）孤岛计数.广搜版
• 岛屿问题（三）最大岛屿的面积
• 岛屿问题（四）孤岛的总面积
• 岛屿问题（五）沉没孤岛
• 岛屿问题（六）高山流水
• 岛屿问题（七）建造最大工岛
• 岛屿问题（八）海岸线计算
• 字符串接龙
• 有向图的完全连通
• 并查集理论基础
• 寻找存在的路线
• 多余的边
• 多余的边II
• 最小生成树之prim
• 最小生成树之Kruskal
• 拓扑排序
• dijkstra朴素版
• dijkstra堆优化版
• Bellman_ford算法
• Bellman_ford之队列优化
• Bellman_ford之判断负权回路
• Bellman_ford之单源有限最短路
• Floyd算法
• A*算法
• 最短路问题总结篇
• 图论总结篇

学习建议

每完成一道题，先关掉题解，用自己的话说出核心思路，再写一遍代码。如果无法解释某个边界或遍历顺序，说明这道题还需要再模拟一遍。

返回算法学习路线 · 上一专题：单调栈 · 下一专题：算法基础