朴素算法Bare Algo

图论

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

算法题

(10)

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

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

200. 岛屿数量

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

133. 克隆图

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

994. 腐烂的橘子

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

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

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

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

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

207. 课程表

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

210. 课程表 II

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

785. 判断二分图

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

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

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

743. 网络延迟时间

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

399. 除法求值

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

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

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

理论知识

(2)

并查集理论基础

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

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

图的遍历

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

图DFSBFS

实际应用

(7)

依赖关系分析

中等

依赖图常做环路检测、拓扑排序与影响分析,提升处理效率。

拓扑排序构建工具工作流依赖

工作流/编排器

中等

工作流图常分析可达路径、关键链路与环路,提升处理效率。

图遍历最短路工作流编排

权限可达性

简单

权限关系图常判断页面、菜单与操作可达性,提升处理效率。

DFSBFS权限路由

关系图可视化

中等

关系图常分析连通群组、推荐链路与距离,提升处理效率。

连通分量最短路可视化关系图

实体合并/聚类

中等

重复实体常按关联关系聚类后统一合并,提升处理效率。

并查集数据清洗用户画像

构建工具依赖图

困难

构建依赖图常分析变更影响范围与循环引用,提升处理效率。

图论构建工具工程化

页面跳转/推荐链路

中等

页面跳转链路常计算最短路径与可达性,提升处理效率。

BFS路由用户体验