图结构进阶：最小生成树、拓扑应用与更高阶建模

---

1. 图进阶真正难在哪里

基础图论里，BFS、DFS、最短路已经足够解决很多问题；但一旦进入进阶阶段，难点会立刻转向“多种结构的联动”：

1. 最小生成树会把图、堆、并查集放到同一个问题里。
2. 拓扑排序会和依赖管理、动态规划、关键路径分析结合。
3. 图不再只是“遍历一遍”，而是要围绕具体业务目标建立合适模型。

这就是为什么图被很多课程看作数据结构和算法之间最明显的交汇点。

2. 最小生成树的目标是什么

对于一个连通无向带权图，最小生成树（MST, Minimum Spanning Tree）要选出 n-1 条边：

1. 让所有顶点连通。
2. 不产生环。
3. 总权值最小。

它非常适合抽象：

1. 通信网络最低铺设成本。
2. 电网、道路、管线最小连通骨架。
3. 聚类算法中的某些底层步骤。

3. Kruskal：按边从小到大选，配合并查集判环

3.1 Go 实现 Kruskal

3.2 Kruskal 的复杂度来自哪里

4. Prim：从一个点出发逐步向外扩展

4.1 Prim 适合什么场景

5. 最小生成树的本质不是模板，而是“贪心 + 无环约束”

6. 拓扑排序不只是排顺序，而是依赖系统的骨架

7. 课程安排问题：判断能否修完全部课程

8. DAG 上的动态规划：为什么拓扑序这么重要

9. 拓扑排序在工程中的几个高频落点

9.1 构建系统

9.2 工作流调度

9.3 数据血缘分析

10. 更高阶建模：同一个问题未必只有一种图模型

11. 最小生成树与最短路径不要混

12. 图进阶这一页的真正收获