朴素算法Bare Algo

图论

图论基础遍历、拓扑排序及最短路径。

算法题

(10)

第 1 阶段:先把图遍历和网格搜索练熟

从岛屿数量、克隆图、腐烂的橘子和二进制矩阵最短路开始,先把 BFS、DFS 和 visited 的基本套路打稳。

200. 岛屿数量

中等
数组深度优先搜索广度优先搜索并查集矩阵

133. 克隆图

中等
哈希表深度优先搜索广度优先搜索图

994. 腐烂的橘子

中等
数组广度优先搜索矩阵

1091. 二进制矩阵中的最短路径

中等
数组广度优先搜索矩阵

第 2 阶段:理解拓扑排序与连通性判断

这一阶段围绕有向图拓扑排序、二分图染色和并查集展开,重点是把“依赖关系”和“集合归并”抽象清楚。

207. 课程表

中等
图深度优先搜索广度优先搜索拓扑排序

210. 课程表 II

中等
图深度优先搜索广度优先搜索拓扑排序

785. 判断二分图

中等
深度优先搜索广度优先搜索并查集图

第 3 阶段:进入带权图与最优化问题

最后处理网络延迟、等式求值和最小生成树,训练最短路、建图抽象以及按边权做全局最优选择。

743. 网络延迟时间

中等
深度优先搜索广度优先搜索图堆最短路

399. 除法求值

中等
深度优先搜索广度优先搜索并查集图最短路

1584. 连接所有点的最小费用

中等
数组并查集图最小生成树

理论知识

(2)

并查集理论基础

理解不相交集合的合并与查询,掌握路径压缩和按秩合并优化

并查集不相交集合路径压缩按秩合并

图的遍历

深度优先搜索(DFS)与广度优先搜索(BFS)的原理与应用

图DFSBFS