• Greedy Algorithms Part One

算法复习笔记：贪心算法与最小生成树 (MST)

一、 贪心算法 (Greedy Algorithm) 核心思想

在每一步选择中，都采取当前状态下最好或最优（最有利）的选择，从而希望导致全局最优解。这种“眼光短浅”（Myopic / Short-sighted）的选择策略虽然在很多复杂的决策问题中无法得到全局最优解，但在特定的数学结构下，它能极其高效地收敛至全局最优方案。最小生成树 (Minimum Spanning Tree, MST) 就是贪心算法取得完美成功的经典范例。

二、 最小生成树与割属性 (Cut Property)

1. 树 (Tree) 的核心性质

一个无向图 $G = (V, E)$ 是树，当且仅当它满足以下等价条件：

• 连通且无环。
• 拥有恰好 $|V| - 1$ 条边（若有 $n$ 个节点，则树有 $n - 1$ 条边）。
• 任何两个节点之间有且仅有一条唯一路径。

2. 最小生成树 (MST) 问题定义

• 输入：无向连通图 $G = (V, E)$，边权为 $w_e$。

• 输出：一棵生成树 $T = (V, E')$，其中 $E' \subseteq E$，使得树的总权重最小：

  $weight(T) = \sum_{e \in E'} w_e$

3. 割属性 (Cut Property) —— 贪心选择的数学基石

【手写笔记订正与深化】

• 原笔记表述：割属性 cut property: $X$ 是最小 MST 与其他 node 之间的 crossing edge 中一定有最短边属于 MST。
• 数学严谨定义： 设边集 $X \subseteq E$ 是某棵最小生成树 $T$ 的子集（即我们已经安全选择的一部分边）。任选一个顶点的子集 $S \subset V$，使得 $X$ 中没有任何边横跨 $S$ 与 $V-S$。 设 $e$ 是所有横跨 $S$ 与 $V-S$ 的边（称为割的交叉边 / Crossing Edges）中**权值最小（最轻）**的边。 则 $X \cup \{e\}$ 必然也是某棵最小生成树的一部分（也就是说，将 $e$ 加入我们的选择是绝对安全的）。

割属性的“交换论证法 (Exchange Argument)”证明：

假设 $X$ 被包含在某棵最小生成树 $T$ 中。我们分两种情况讨论：

1. 如果边 $e$ 已经属于 $T$，则 $X \cup \{e\} \subseteq T$ 显然成立。

2. 如果边 $e \notin T$，我们将 $e$ 临时添加进树 $T$。此时，由于树的性质，添加一条边必然会在 $T \cup \{e\}$ 中产生一个唯一的环。

   • 因为 $e$ 的两个端点分别在 $S$ 和 $V-S$ 中，这个环必须从 $S$ 走到 $V-S$，再走回来。因此，该环上必定存在另一条也横跨 $S$ 与 $V-S$ 的边 $e'$（如图 1 所示）。

   • 因为 $X$ 在 $S$ 与 $V-S$ 之间没有交叉边，所以这另一条跨越边 $e'$ 必然不属于 $X$（即 $e' \notin X$）。

   • 我们构造一棵新树 $T' = T \cup \{e\} \setminus \{e'\}$。

   • 由于 $e$ 是跨越该割的最轻边，所以必然有 $w(e) \le w(e')$。

   • 新树的权重为：

     $weight(T') = weight(T) + w(e) - w(e') \le weight(T)$

   • 由于 $T$ 已经是最小生成树（权重不可能更低），因此必然有 $weight(T') = weight(T)$，即 $T'$ 也是一棵最小生成树。

   • 因为 $e' \notin X$，所以 $X \subseteq T'$。因此 $X \cup \{e\} \subseteq T'$ 成立。证明完毕。

二、 最小生成树：Kruskal 算法 (Kruskal’s Algorithm)

【手写笔记还原 · 必背核心】

• 核心思想：重复添加下一条不会产生环的**最轻（权重最小）**的边。

1. Kruskal 算法执行流程

1. 将图 $G=(V, E)$ 中所有的边按照权重从小到大进行排序。
2. 初始化，将每个顶点都看作一个独立的连通分量（一棵孤立的树）。
3. 顺序遍历排序后的边：若当前边的两个端点属于不同的连通分量（即加入该边不会产生环），则选择这条边，并合并这两个连通分量；否则，舍弃这条边。
4. 重复上述步骤，直到选出了 $|V| - 1$ 条边。

2. 核心伪代码 (★ 考试必背)

【手写笔记强调】：这个伪代码必须要记住！特别注意：添加边时一定要使用 union 操作来合并连通分量，否则后续的成环判断 find(u) != find(v) 就会失效！

procedure kruskal(G, w)
Input: 连通无向图 G = (V, E)，边权 w
Output: 由边集 X 定义的最小生成树 (MST)

for all u ∈ V:
    makeset(u)                  // 初始化：每个节点自成一个独立集合

X = {}                          // 存储 MST 的边集
Sort the edges E by weight      // 将边按权重从小到大排序

for all edges {u, v} ∈ E, in increasing order of weight:
    if find(u) != find(v):      // 关键判断：如果不相等，说明 u 和 v 不在同一连通分量中（不产生环）
        add edge {u, v} to X    // 将边安全地加入 MST
        union(u, v)             // 极其重要！必须调用 union 合并这两个分量

三、 并查集 (Disjoint Set) 数据结构

在实现 Kruskal 算法时，我们需要频繁地判断两个节点是否在同一个连通分量中（避免成环），并在加入边后合并两个连通分量。并查集正是为了支持这两种操作而生的高效数据结构。

1. 核心操作

• makeset(x)：创建一个只包含单个元素 $x$ 的新集合。
• find(x)：寻找 $x$ 所在树的根节点（即该集合的“代表元素”）。
• union(x, y)：将 $x$ 所在的集合与 $y$ 所在的集合合并。

2. 深度解答笔记中的疑问

【疑问一】并查集（Disjoint Set）中子节点只能有两个吗？ 【解答】 不是！ 并查集内部是用多叉树（有向树）*来存储集合的。这与二叉树截然不同，并查集中的一个节点可以拥有*任意多个子节点。 因为并查集只关心“往上找爸爸”（每个节点只存储一个指向父节点的指针 parent[x]），所以它根本不在乎自己有多少个子节点。一个根节点指向它的孩子可以有 1 个、2 个，甚至成百上千个。

【疑问二】union(X, Y) 时，如果 $X$ 已经有两个子节点了，怎么办？ 【解答】 完全不冲突，直接连接即可！ union(X, Y) 的核心本质是让其中一个集合的根节点指向另一个集合的根节点。 例如，如果 $r_x = find(X)$，$r_y = find(Y)$。合并时我们只需将 $\pi(r_x) = r_y$（即把 $r_x$ 的父指针指向 $r_y$）。 无论 $r_x$ 此时有多少个孩子节点，它们依然通过 $r_x$ 间接地连向了新的老祖宗 $r_y$。这只需要修改一个指针，孩子节点完全不需要做任何改动。

3. 按秩合并 (Union by Rank)

如果盲目合并，并查集的树有可能会退化为一条长长的链，导致 find 操作退化为 $O(|V|)$。 为了防止树过深，我们引入秩（Rank）*的概念。在合并时，我们总是让*矮树的根节点指向高树的根节点。

• Rank的定义：$rank(x)$ 表示以 $x$ 为根节点的子树的理论最大高度。
• 合并规则：
  • 若 $rank(r_x) < rank(r_y)$，则让 $\pi(r_x) = r_y$（树高不变）。
  • 若 $rank(r_x) > rank(r_y)$，则让 $\pi(r_y) = r_x$（树高不变）。
  • 若 $rank(r_x) = rank(r_y)$，则可任意指定一个为根，并将新根的 rank 值加 1：$rank(r_y) = rank(r_y) + 1$。

并查集的经典按秩合并伪代码实现

# 初始化：每个元素单独成树
def makeset(x):
    parent[x] = x
    rank[x] = 0

# 寻找代表元素：沿着父节点指针一路向上，直到根节点
def find(x):
    curr = x
    while curr != parent[curr]:
        curr = parent[curr]
    return curr

# 按秩合并
def union(x, y):
    root_x = find(x)
    root_y = find(y)
    
    if root_x == root_y:
        return  # 已经在同一个集合中
        
    # 让矮树（Rank小）指向高树（Rank大）
    if rank[root_x] > rank[root_y]:
        parent[root_y] = root_x
    else:
        parent[root_x] = root_y
        if rank[root_x] == rank[root_y]:
            rank[root_y] += 1  # 只有当高度相同时，合并后高度才会增加1

四、 路径压缩 (Path Compression) 与 Kruskal 时间复杂度

1. 路径压缩的具体做法

在执行 find(x) 的过程中，我们需要顺着祖先链一路往上爬。 路径压缩的绝妙之处在于：在我们找到了根节点 root 之后，在回溯时，将路径上经过的每一个节点的父指针都直接指向根节点（如图 2 所示）。

带有路径压缩的 find 递归实现：

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x]) # 递归寻找并直接修改父指针（路径压缩）
    return parent[x]

2. 深度解答笔记中的疑问

【疑问三】Kruskal 算法的运行时间是 $O(|E| \log |V|)$，这是怎么来的？

【解答】 我们来对 Kruskal 算法的每一个步骤进行拆解：

1. 边排序：原图中有 $|E|$ 条边。由于需要按照权重从小到大处理边，排序消耗的时间为 $O(|E| \log |E|)$。
   • 在简单无向图中，边的数量最多为 $|V|^2$，所以 $\log |E| \le \log(|V|^2) = 2 \log |V|$。
   • 因此，排序的复杂度可以写为 $O(|E| \log |V|)$。
2. 初始化并查集：执行了 $|V|$ 次 makeset 操作，耗时 $O(|V|)$。
3. 遍历边进行并查集操作：对于排序好的每条边，我们需要：
   • 调用 $2|E|$ 次 find 检查两个端点。
   • 调用最多 $|V| - 1$ 次 union 进行连通分量合并。

如果不使用路径压缩（仅使用按秩合并）： 每次 find 的最坏情况树高为 $\log |V|$。并查集部分的总开销为 $O(|E| \log |V|)$。

如果同时使用按秩合并与路径压缩： 此时并查集的单次操作均摊时间复杂度降低到了极其惊人的 $O(\alpha(|V|))$（其中 $\alpha$ 是反阿克曼函数，对于宇宙中所有的实际数据，该值都小于等于 4，可视为常数）。 并查集部分的实际开销降为：$O(|E| \alpha(|V|))$。

结论： 即使并查集优化到了接近线性时间，整个 Kruskal 算法的瓶颈仍然在第一步的“边排序”上！ 排序的 $O(|E| \log |V|)$ 加上并查集的 $O(|E| \alpha(|V|))$，最终的总运行时间依然是 $O(|E| \log |V|)$。

五、 Prim 算法

1. 核心思想

Prim 算法是另一种寻找 MST 的贪心策略。它的中间状态 $X$ 始终保持为一棵单一的树。 我们从任意一个起点节点开始，每次都选择横跨“当前已构建的树 $S$”与“剩余未加入的节点 $V-S$”之间最轻的那条边，将这条边加入生成树，并把对应的外接节点拉入 $S$。

2. Prim 算法 vs Dijkstra 算法

由于两者都利用了优先队列（堆）来动态维护最优节点，它们的伪代码极为相似。但它们的键值（Key / Priority）更新规则有着本质的不同：

• Dijkstra 算法：维护的是从源点到节点 $z$ 的全局最短路径累积长度：

  $\text{dist}[z] = \text{dist}[v] + w(v, z)$

• Prim 算法：维护的是节点 $z$ 到当前已建成的生成树集合 $S$ 的最短单条边权重：

  $\text{cost}[z] = w(v, z)$

Prim 算法伪代码

def prim(G, w, start_node):
    # 初始化
    for u in G.V:
        cost[u] = infinity
        parent[u] = None
    
    cost[start_node] = 0
    # 将所有顶点放入优先队列（最小堆），以 cost 值作为 key
    PQ = make_queue(G.V, key=cost)
    
    while not PQ.is_empty():
        v = PQ.extract_min()  # 弹出当前距离生成树最近的节点
        
        for neighbor, weight in G.adj[v]:
            # 如果邻居节点还在队列中，且找到了更短的连接到当前生成树的边
            if neighbor in PQ and cost[neighbor] > weight:
                cost[neighbor] = weight
                parent[neighbor] = v  # 记录生成树中的前驱节点
                PQ.decrease_key(neighbor, new_key=weight)

六、 重点精选例题与详细解答

为了帮助你彻底巩固这部分知识，我将带你详细剖析三个经典的例题。

例题一：并查集操作追踪 (课后题 5.11 延伸)

【题目】 起初有 8 个单元素集合：$\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}, \{7\}, \{8\}$。 使用路径压缩和按秩合并。 约定：当合并两棵秩相同的树时，总是让编号小的根节点指向编号大的根节点。 请写出执行以下操作序列后，并查集的树形结构： union(1,2), union(3,4), union(5,6), union(7,8), union(1,4), union(6,7), union(4,5), find(1)

【详细解析步骤】

1. 初始状态：每个节点自成一根，rank 均为 0。
2. union(1,2)：等秩合并。1 指向 2。
   • $\pi(1) = 2$，$rank(2) = 1$。
3. union(3,4)：等秩合并。3 指向 4。
   • $\pi(3) = 4$，$rank(4) = 1$。
4. union(5,6)：等秩合并。5 指向 6。
   • $\pi(5) = 6$，$rank(6) = 1$。
5. union(7,8)：等秩合并。7 指向 8。
   • $\pi(7) = 8$，$rank(8) = 1$。
6. union(1,4)：
   • $find(1)$ 得到根节点 2（$rank(2)=1$），$find(4)$ 得到根节点 4（$rank(4)=1$）。
   • 两根等秩合并，小编号 2 指向大编号 4。
   • $\pi(2) = 4$，$rank(4) = 2$。此时以 4 为根的树包含：$1 \rightarrow 2 \rightarrow 4$ 和 $3 \rightarrow 4$。
7. union(6,7)：
   • $find(6)$ 得到根 6（$rank=1$），$find(7)$ 得到根 8（$rank=1$）。
   • 等秩合并，小编号 6 指向大编号 8。
   • $\pi(6) = 8$，$rank(8) = 2$。
8. union(4,5)：
   • $find(4)$ 得到根 4（$rank(4)=2$）。
   • $find(5)$ 得到根 8（$rank(8)=2$，因为 5 的爸爸是 6，6 的爸爸现在是 8）。
   • 两根等秩合并，4 指向 8。
   • $\pi(4) = 8$，$rank(8) = 3$。
9. find(1)：
   • 寻找 1 的根节点：我们顺着 $1 \rightarrow 2 \rightarrow 4 \rightarrow 8$ 找到了老祖宗 8。
   • 触发路径压缩：将路径上所有遍历到的节点（1, 2, 4）的父指针直接连向 8。
   • 即：$\pi(1) = 8$，$\pi(2) = 8$，$\pi(4) = 8$。

【最终结构】 所有节点最终直接指向根节点 8（除 3 仍指向 4，5、6 仍指向 8，7 仍指向 8 外，大部分已被完美扁平化）。

例题二：最小生成树的动态更新 (Discussion 4 / 课后题 5.22)

【题目】 给定无向连通图 $G = (V, E)$ 及其一棵已求得的最小生成树 $T = (V, E')$。假设所有边权均不相同。 现在，某条特定边 $e$ 的权重从 $w(e)$ 变为了一个新值 $\hat{w}(e)$。 请设计一个线性时间复杂度 $O(|V| + |E|)$ 的算法，快速更新这棵最小生成树 $T$。

我们需要分以下四种情况进行分类讨论：

情况 (a)：$e \in E'$ 且 $\hat{w}(e) < w(e)$（树中某条边变得更轻了）

• 分析：边 $e$ 本来就在最小生成树中，现在它的权重进一步变小，它对生成树的贡献只会增强，绝不可能被其他更重的边替换。同时，由于只改变了权重而没有引入新边，所以图中不会产生新的环。
• 更新算法：树的结构保持完全不变，仅更新该边权重的值。
• 证明：根据割属性，原本 $e$ 就是某割的最轻跨越边，现在变轻后依然是。
• 时间复杂度：$O(1)$。

情况 (b)：$e \notin E'$ 且 $\hat{w}(e) < w(e)$（树外某条边变得更轻了）

• 分析：边 $e = (u, v)$ 原本不属于树 $T$。现在它变轻了，可能会“逆袭”挤掉树中的某些边。 如果我们把 $e$ 加入到树 $T$ 中，会在树中形成一个唯一的环 $C$。根据环属性（Cycle Property），这个环上最重的边必须被剔除。
• 更新算法：
  1. 在树 $T$ 中，使用 DFS 或 BFS 找到从节点 $u$ 到 $v$ 的唯一路径，该路径与边 $e$ 共同构成一个环 $C$。
  2. 在这个环中，找到除了 $e$ 之外权值最大的边 $e_{\max}$。
  3. 若 $\hat{w}(e) < w(e_{\max})$，则用 $e$ 替换 $e_{\max}$（即 $T' = T \cup \{e\} \setminus \{e_{\max}\}$）；否则，生成树保持不变。
• 时间复杂度：由于树 $T$ 只有 $|V| - 1$ 条边，在其上跑 DFS 寻找路径只需 $O(|V|)$ 的时间。

情况 (c)：$e \in E'$ 且 $\hat{w}(e) > w(e)$（树中某条边变得更重了）

• 分析：边 $e = (u, v)$ 原本在树中，现在变重了，可能需要被树外的某条更轻的横跨边替换。 如果我们把 $e$ 从树 $T$ 中移除，树会被分裂成两棵不连通的子树 $T_1$ 和 $T_2$（这实际上划分出了一个割 $(S, V-S)$）。为了重新连通这两部分，我们需要在所有跨越该割的边中找一条最轻的。
• 更新算法：
  1. 将 $e$ 从 $T$ 中临时移除，通过 DFS 标记其中一棵子树包含的节点集合 $S$，则另一部分节点集为 $V - S$。
  2. 遍历原图 $G$ 中所有的边，筛选出所有横跨 $S$ 与 $V-S$ 的边（Crossing Edges）。
  3. 在这些横跨边中，找出新的权值最小边 $e_{\min}$（包含更新权重后的 $e$）。
  4. 令新的最小生成树为 $T' = (T \setminus \{e\}) \cup \{e_{\min}\}$。
• 时间复杂度：
  • 标记子树节点：$O(|V|)$。
  • 筛选并寻找最轻横跨边：需要遍历原图中的所有边，耗时 $O(|E|)$。
  • 总时间复杂度为：$O(|V| + |E|)$。

情况 (d)：$e \notin E'$ 且 $\hat{w}(e) > w(e)$（树外某条边变得更重了）

• 分析：边 $e$ 本来就因为太重而被排斥在树外，现在它变得更重了，更加不可能进入最小生成树中。
• 更新算法：树的结构保持完全不变。
• 时间复杂度：$O(1)$。

例题三：区间最大调度贪心反例 (Discussion 4 问题 1)

【题目】 在区间调度问题中，我们的目标是从多个有重叠的区间中选出最大数量的互不冲突的区间。我们已知“总是选择结束时间最早（Earliest Finish Time）”的贪心策略是正确的。请给出反例，证明以下两种直观的贪心策略是错误的：

• 策略一：总是选择最早开始时间（Earliest Start Time）的区间。
• 策略二：总是选择区间长度最短（Shortest Length）的区间。

【详细反例推导】

1. 策略一（Earliest Start Time）的反例：

我们构造以下三个区间：

• 区间 A: $[0, 10]$ （开始极早，但极长）
• 区间 B: $[1, 2]$
• 区间 C: $[3, 4]$
• 贪心选择：该策略首先选中 A。因为 A 与 B、C 都冲突，最终只能选择一个区间 $\{A\}$。
• 最优解：选择不冲突的 B 和 C，得到解 $\{B, C\}$，最大区间数为 2。贪心算法失败。

2. 策略二（Shortest Length）的反例：

我们构造以下三个区间：

• 区间 A: $[0, 3]$ （长度为 3）
• 区间 B: $[2, 4]$ （长度为 2，最短）
• 区间 C: $[3, 6]$ （长度为 3）
• 贪心选择：由于 B 的长度最短，策略首先选择 B。选择 B 之后，与之重叠的 A 和 C 都无法选择。最终解为 $\{B\}$，区间数为 1。
• 最优解：选择 A 和 C，它们相互兼容（A 在 3 结束，C 在 3 开始），得到解 $\{A, C\}$，最大区间数为 2。贪心算法失败。