xxx 最小生成树的 Reverse-Delete 算法 题目描述 给定一个连通无向图 \( G = (V, E) \)，每条边 \( e \in E \) 有一个权重 \( w(e) \)。要求通过删除边的方式，逐步构造一棵最小生成树（MST），使得生成树的边权重之和最小。 解题过程 问题理解 目标是从原图中删去部分边，保留 \( |V|-1 \) 条边构成生成树，且总权重最小。 与 Kruskal 或 Prim 算法的“加边”思路相反，Reverse-Delete 采用“删边”策略。 核心思想 按边权重从大到小排序，依次检查每条边：若删除后图仍连通，则删除该边（因其权重大，删除可减少总权重）。 最终剩余的边构成最小生成树。 算法步骤 步骤 1：初始化 将图的所有边按权重降序排列，得到边列表 \( E_ {\text{sorted}} \)。 初始化当前边集 \( T = E \)（即开始时保留所有边）。 步骤 2：遍历边并检查 遍历 \( E_ {\text{sorted}} \) 中的每条边 \( e \)： 临时从 \( T \) 中移除 \( e \)，检查图 \( (V, T \setminus \{e\}) \) 是否仍连通（通过 DFS/BFS 判断）。 若仍连通，说明 \( e \) 冗余（删除不影响连通性），则永久删除：\( T = T \setminus \{e\} \)。 否则保留 \( e \)（因为删除会导致图不连通）。 步骤 3：终止条件 当遍历完所有边时，\( T \) 中剩余的边即为最小生成树。 关键点说明 连通性检查 ：每次删除边前需验证连通性，确保不破坏生成树性质。 正确性依据：若一条边在生成树中不是桥（即删除后图仍连通），则可安全删除。 时间复杂度：排序需 \( O(|E| \log |E|) \)，每次连通性检查需 \( O(|V| + |E|) \)，总复杂度为 \( O(|E| (|V| + |E|)) \)。可通过并查集优化至 \( O(|E| \log |V|) \)。 示例演示 考虑一个 4 顶点图，边权重为： (A-B, 1), (B-C, 2), (C-D, 3), (A-C, 4) 按权重降序排序边：[ (A-C,4), (C-D,3), (B-C,2), (A-B,1) ] 检查 (A-C,4)：删除后图仍连通（通过 B→C→D 和 A→B 连通），故删除。 检查 (C-D,3)：删除后图仍连通（A→B→C 存在），故删除。 检查 (B-C,2)：删除后图不连通（A-B 和 C-D 分离），故保留。 检查 (A-B,1)：删除后图不连通，故保留。 最终 MST 为 {(A-B,1), (B-C,2)}，总权重 3。 总结 Reverse-Delete 算法通过逆向删除冗余边构建 MST，其正确性依赖于“删除非桥边不破坏连通性”的图论性质。尽管效率不如 Kruskal 或 Prim，它提供了独特的逆向思维视角。