xxx 最小生成树问题（Reverse-Delete算法）

题目描述
最小生成树（Minimum Spanning Tree, MST）是图论中的经典问题：给定一个连通无向图 \(G = (V, E)\)，每条边有一个权重，要求找到一个边的子集，使得这些边构成一棵树（连通且无环），并且总权重最小。Reverse-Delete算法是求解MST的一种方法，其核心思想是按权重从大到小的顺序删除边，但仅当删除后不破坏图的连通性时才执行删除，最终剩下的边构成最小生成树。

解题过程

1. 算法思路
   Reverse-Delete算法是Kruskal算法的“逆过程”：

   • Kruskal算法：按权重从小到大添加边，避免成环。
   • Reverse-Delete算法：按权重从大到小尝试删除边，仅当删除后图仍连通时才删除（即删除的是“冗余”的边）。
   • 关键点：删除边时必须保证图始终连通，因此需要动态检查连通性（通常用并查集或DFS/BFS）。

2. 步骤详解

   • 步骤1：将图中所有边按权重从大到小排序。
   • 步骤2：从权重最大的边开始，依次检查每条边：
     • 暂时移除当前边，检查图是否仍连通（例如用BFS/DFS或并查集判断）。
     • 若仍连通，说明当前边是冗余的（即存在另一条路径连接边的两个端点），保留删除操作。
     • 若不连通，说明当前边是必要的（是连接两个部分的唯一边），撤销删除（保留该边）。
   • 步骤3：重复步骤2直到处理完所有边，最终剩下的边构成最小生成树。

3. 实例演示
   考虑一个简单图（顶点为A、B、C、D），边及权重如下：

   • AB: 1, BC: 2, CD: 3, DA: 4, AC: 5
     按权重排序边：AC(5) > DA(4) > CD(3) > BC(2) > AB(1)
   • 检查AC(5)：删除后图仍连通（可通过A-D-C或A-B-C连接），删除AC。
   • 检查DA(4)：删除后图仍连通（可通过A-B-C-D连接），删除DA。
   • 检查CD(3)：删除后图不连通（C和D之间无其他路径），保留CD。
   • 检查BC(2)：删除后图不连通（B和C之间无其他路径），保留BC。
   • 检查AB(1)：删除后图不连通，保留AB。
     最终MST包含边AB、BC、CD，总权重为1+2+3=6。

4. 正确性说明

   • 定理：在任意连通图中，删除一条权重最大的边（且不破坏连通性）不会影响最小生成树的构造，因为MST一定不包含这样的冗余边。
   • 算法保证每一步删除的边都不在MST中，最终剩下的边是连接所有顶点的最小权重边集。

5. 复杂度分析

   • 排序边：\(O(|E| \log |E|)\)。
   • 每次删除检查连通性：最坏情况需 \(O(|V| + |E|)\)（如用BFS/DFS）。
   • 总复杂度：\(O(|E| \cdot (|V| + |E|))\)，可通过并查集优化到 \(O(|E| \log |E|)\)（并查集检查连通性均摊 \(O(\alpha(|V|))\)）。

6. 对比其他MST算法

   • 与Kruskal/Prim相比，Reverse-Delete在实际中较少使用，因为需要预先保留所有边，且删除检查开销较大。
   • 适用场景：适合边数较多但最终MST边数较少的图（如近乎完全的图）。