罗罗编程学习记录
本页内容 展开查看

02.4.2 图论与并查集

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.4 树与图

这个知识域解决什么问题

图是多对多关系的抽象。本知识域围绕 图表示与遍历 → 拓扑排序与环检测 → 并查集 → 最短路径与最小生成树 四条主线展开;先建立邻接表/邻接矩阵与 DFS/BFS 框架,再处理依赖顺序、动态连通与网络代价问题。

知识地图

图表示与 DFS/BFS(1)
  → 拓扑排序与环检测(2)
    → 并查集(3)
      → 最短路径与最小生成树(4)

子主题

编号 子主题 核心内容 题数
02.4.2.1 图表示与 DFS/BFS 邻接表/矩阵、DFS 递归与迭代、BFS、visited 时机、连通分量、岛屿、克隆图、二分图、多源 BFS 20
02.4.2.2 拓扑排序与环检测 Kahn 入度算法、DFS 逆后序、三色判环、课程表、拓扑唯一性、DAG 性质与关键路径 20
02.4.2.3 并查集 find 根、路径压缩、按秩/大小合并、连通分量、冗余连接、账户合并、等式判定、α(n) 复杂度 20
02.4.2.4 最短路径与最小生成树 BFS 无权最短路、Dijkstra、Bellman-Ford、Floyd、Kruskal、Prim、负权负环、网络延迟 20

合计 80 题。 每题按「一句话结论 → 概念解释 → 原理流程 → 代码/图示 → 常见误区 → 追问(带答案)」组织;代码以 Java 为主,标注复杂度口径与边界条件。

学习路径

先 1 掌握图表示与两种遍历框架,2 用拓扑排序处理依赖与判环,3 用并查集解决动态连通与归并,最后 4 按权值条件选择最短路与 MST 算法。

自检

  • [ ] 能根据边密度选择邻接表或邻接矩阵,并写出 DFS/BFS
  • [ ] 能解释 visited 入结构即标记的原因
  • [ ] 能手写 Kahn 拓扑排序并判环,理解 DFS 逆后序
  • [ ] 能实现路径压缩 + 按秩合并的并查集,报出 α(n) 复杂度
  • [ ] 能区分 Dijkstra、Bellman-Ford、Floyd 的适用条件
  • [ ] 能写 Kruskal(DSU 判环)与 Prim,并说明选型
  • [ ] 每题能报出时间、空间与口径,并列边界用例