贪心算法(1)：最小生成树

本文为SJTU-AI2615算法课程的知识点复习，主要复习内容为最小生成树算法（Prim 与 Kruskal 算法），以及并查集。

贪心算法（Greedy Algorithm）

总体特点

• 通过局部最优决策逐步逼近全局最优解，决策不可回退。
• 如最短路径的 Dijkstra 算法。

作业调度问题

• ​输入：$n$ 项作业，每项作业包含处理时间 $s_j$ 和截止时间 $d_j$。
• ​贪心策略：优先处理截止时间最早的作业。
• ​最优性证明：
  • ​核心逻辑：若贪心策略无法完成所有作业，则任何其他策略也无法完成。
  • ​矛盾构造：假设存在其他可行方案，可通过调整作业顺序证明贪心策略的必然最优性。

最小生成树（MST）

Prim 算法

• ​核心步骤：
  1. ​初始化：任选起点，记录顶点到树的最小边权。
  2. ​扩展：每次选择连接树与非树顶点的最小权边。
  3. ​更新：调整非树顶点到树的最小边权。

• ​正确性证明：
  • 核心逻辑：证明每一步构造的树是一棵完整的 MST 的一部分。
  • ​交换论证：若存在更优生成树，可通过替换边使其包含当前选择的边。

这是贪心算法的常见证明思路。

• ​时间复杂度：$\bm{O(|E| + |V| \log |V|)}$（斐波那契堆优化）

Kruskal 算法

• ​核心步骤：
  1. ​排序：按边权升序排列所有边。
  2. ​选择：依次选择不形成环的边加入生成树。
  3. ​检测环：通过并查集（Union-Find）高效实现。

• ​正确性证明：类似 Prim 算法

• ​时间复杂度：
  • 排序：$O(|E| \log |E|)$
  • 查组：$2|E| \cdot O(\log |V|)$
  • 合并：$|V| \cdot O(1)$
  • 总时间复杂度：$\bm{O(|E| \log |V|)}$

并查集（Union-Find）

基本操作

• ​Find：查询元素所属集合的根节点。
• ​Union：合并两个集合。

优化策略

按秩合并（Union by Rank）

• ​策略：将较小树合并到较大树，控制树高。
• ​效果：树高增长缓慢，最大树高为 $O(\log n)$ 。

路径压缩（Path Compression）

• ​策略：在 Find 操作中将路径上的节点直接链接到根节点。
• ​效果：Find 操作的摊还时间复杂度为 $O(\alpha (n))$。

时间复杂度分析

• 关键引理：

  1. 父节点的秩严格大于子节点的秩。
  2. 秩为 $r$ 的树 至少有 $2^r$ 个节点。
  3. 组数最多为 $\log^* n$。
  4. 组 $[k + 1, 2^k]$ 最多有 $n / 2^k$ 个节点。

• 关键结论：（一共做 $m$ 次 Find 操作）

  • Find 本身负责指向根节点的操作 $O(m)$ 次。
  • 每次 Find 最多 $\log^* n$ 次跨组操作，总代价 $O(m \log^* n)$。
  • 节点负责组内操作，每组最多 $n$ 次操作，总代价 $O(n \log^* n)$。

• 时间复杂度：

  • 任何 $m$ 次 Find 操作的时间代价为 $O(m \log^* n + n \log^* n)$。
  • 因此 Find 操作的摊还时间复杂度为 $\bm{O(\log^* n)}$。

算法对比总结

​算法	​适用场景	​核心策略	​时间复杂度
​Prim	稠密图最小生成树	顶点扩展 + 优先队列	$O(\vert E \vert + \vert V \vert \log \vert V \vert)$
​Kruskal	稀疏图最小生成树	边排序 + 并查集	$O(\vert E \vert \log \vert V \vert)$
​Dijkstra	非负权最短路径	贪心扩展 + 优先队列	$O(\vert E \vert + \vert V \vert \log \vert V \vert)$
​BFS	无权图最短路径	分层扩展	$O(\vert V \vert + \vert E \vert)$
​Bellman-Ford	含负权边最短路径	松弛迭代	$O(\vert V \vert \cdot \vert E \vert)$
​DFS	连通性检测 / 拓扑排序 / 环路检测	深度优先递归	$O(\vert V \vert + \vert E \vert)$

注：本文中所有图片均来自张宇昊老师的课程PPT。