(a-b, 1), (b-c, 2), (c-d, 3), (d-a, 4), (a-c, 5)

xxx 最小生成树的 Reverse-Delete 算法 题目描述 给定一个连通无向图 \( G = (V, E) \) 和边权函数 \( w: E \to \mathbb{R} \)，要求找到一棵最小生成树（MST）。Reverse-Delete 算法通过按边权降序迭代删除边，并保证删除后图仍连通，最终得到 MST。请详细讲解该算法的步骤、正确性证明及复杂度分析。 解题过程 1. 算法核心思想 Reverse-Delete 是 Kruskal 算法的“逆过程”： Kruskal 按边权升序逐步添加边，避免环。 Reverse-Delete 按边权降序逐步删除边，保证连通性。 关键观察 ：若某边是当前图中权值最大的边，且删除后图仍连通，则该边不可能出现在任何 MST 中（由环性质可证）。 2. 算法步骤 初始化 ：将图 \( G \) 的所有边按权值降序排序。 迭代删边 ： 遍历排序后的边，对当前边 \( e \)： 临时从图中移除 \( e \)。 检查图是否仍连通（用 DFS/BFS 判断）。 若连通，则永久删除 \( e \)（因为 \( e \) 是当前最大权边且非必要）。 否则保留 \( e \) 并继续。 终止条件 ：遍历完所有边，剩余边构成 MST。 3. 逐步示例 考虑以下无向图（顶点集 \( V = \{a,b,c,d\} \)，边权如图）： 步骤 ： 按权降序排序边： \((a-c,5), (d-a,4), (c-d,3), (b-c,2), (a-b,1)\) 检查 \( a-c \)（权 5）： 删除后图仍连通？是 → 永久删除。 检查 \( d-a \)（权 4）： 删除后图仍连通？是 → 永久删除。 检查 \( c-d \)（权 3）： 删除后图仍连通？否（断开 \( d \)）→ 保留。 检查 \( b-c \)（权 2）： 删除后图仍连通？否（断开 \( b \)）→ 保留。 检查 \( a-b \)（权 1）： 删除后图仍连通？否 → 保留。 剩余边：\((c-d,3), (b-c,2), (a-b,1)\)，构成 MST（总权值 6）。 4. 正确性证明 安全边定理 ：若边 \( e \) 是当前图中权值最大的边，且 \( e \) 在某个环上，则存在不包含 \( e \) 的 MST。 证明：假设所有 MST 都包含 \( e \)，则删除 \( e \) 会将树分成两棵子树。因 \( e \) 在环上，存在另一条边 \( f \) 连接这两子树，且 \( w(f) \leq w(e) \)。用 \( f \) 替换 \( e \) 得到更小或相等权值的生成树，矛盾。 Reverse-Delete 仅删除这样的安全边，因此最终得到 MST。 5. 复杂度分析 排序边：\( O(|E| \log |E|) \)。 每次连通性检查（DFS/BFS）：\( O(|V| + |E|) \)。 最坏需检查 \( |E| \) 次 → 总复杂度 \( O(|E| (|V| + |E|)) \)。 优化：用动态连通性数据结构（如并查集维护补图）可降至 \( O(|E| \log |V|) \)，但实现复杂。 6. 总结 Reverse-Delete 提供了与 Kruskal 对偶的 MST 求解方法，适合理解 MST 的环性质。 实际应用中，由于高效连通性检查的实现复杂度，常优先选择 Kruskal 或 Prim 算法。