xxx 最小生成树问题（Reverse-Delete算法） 题目描述 ： 给定一个连通无向图 \( G = (V, E) \)，每条边 \( e \in E \) 有一个权重 \( w(e) \)。要求从图中删除边，使得最终剩余的边构成一棵最小生成树（MST），即树的权重和最小，且保持图连通。Reverse-Delete算法通过逐步删除权重最大的边来实现这一目标，但需确保删除后不破坏图的连通性。 解题过程 ： 算法思想 ： 与Kruskal算法（逐步添加边）相反，Reverse-Delete算法从完整的图开始，按权重降序尝试删除边。若删除某边后图仍连通，则保留删除操作；否则保留该边。最终剩余的边构成MST。 关键点：删除边时必须检查图的连通性，避免断开图。 步骤详解 ： 步骤1 ：将边按权重从大到小排序。例如，若边权重为 \( [ 1, 2, 3, 4 ] \)，则处理顺序为权重4、3、2、1的边。 步骤2 ：遍历排序后的边，对当前边 \( e \)： 临时移除 \( e \)，检查图是否仍连通（通过DFS/BFS判断）。 若连通，则永久删除 \( e \)（因为权重大的边被优先移除，减少总权重）。 若不连通，则保留 \( e \)（该边是连接两个分量的必需边）。 步骤3 ：重复步骤2，直到处理完所有边。剩余边即为MST。 举例说明 ： 假设图有顶点 \( \{A, B, C\} \)，边 \( AB \)（权重1）、\( BC \)（权重2）、\( AC \)（权重3）。 排序边：\( AC(3) \)、\( BC(2) \)、\( AB(1) \)。 处理 \( AC \)：删除后图仍连通（通过 \( AB \) 和 \( BC \) 连接），故删除。 处理 \( BC \)：删除后图断开（\( B \) 孤立），故保留。 处理 \( AB \)：删除后图断开（\( A \) 孤立），故保留。 MST包含 \( AB \) 和 \( BC \)，总权重为3。 算法正确性 ： 基于MST性质：若一条边是图中某环的最大权重边，则它一定不在MST中。Reverse-Delete每次删除的边均为当前环中的最大权重边，符合这一性质。 复杂度分析 ： 排序边：\( O(|E| \log |E|) \)。 每次连通性检查（DFS/BFS）：\( O(|V| + |E|) \)。 总复杂度：\( O(|E| (|V| + |E|)) \)，可通过并查集优化连通性检查至 \( O(|E| \log |E|) \)。