xxx 最小生成树的 Reverse-Delete 算法 题目描述 给定一个连通无向图 \( G = (V, E) \)，每条边 \( e \in E \) 有一个权重 \( w(e) \)。目标是找到图 \( G \) 的一棵最小生成树（MST），即一个包含所有顶点的连通无环子图，且其所有边的权重之和最小。Reverse-Delete 算法是一种基于“删除边”的策略来求解最小生成树的方法。 解题过程 算法核心思想 Reverse-Delete 算法与 Kruskal 算法的“加边”思路相反，它从所有边构成的图开始，按权重从大到小的顺序尝试删除边。如果删除某条边后图仍然连通，则保留该删除操作（因为该边不是保持连通性所必需的）；否则撤销删除（说明该边是当前连通性的关键）。最终剩下的边构成最小生成树。 关键步骤详解 步骤1：初始化 将图 \( G \) 的所有边按权重从大到小排序，得到边序列 \( E_ {\text{sorted}} \)。 初始化当前边集合 \( T = E \)（即开始时包含所有边）。 步骤2：遍历边并尝试删除 按顺序遍历 \( E_ {\text{sorted}} \) 中的每条边 \( e \)： 临时从 \( T \) 中移除 \( e \)，检查剩余图 \( (V, T \setminus \{e\}) \) 是否仍连通（通过 DFS/BFS 判断）。 若仍连通，说明 \( e \) 冗余，正式删除（即更新 \( T = T \setminus \{e\} \)）。 若不连通，说明 \( e \) 是必要的，保留该边（不修改 \( T \)）。 步骤3：终止条件 当所有边遍历完成后，\( T \) 即为最小生成树的边集。 正确性证明（简要说明） 算法保证最终子图连通且无环（因为删除边时始终维护连通性，且删除冗余边不会引入环）。 根据最小生成树的切割性质：若一条边是当前图中某切割的唯一最大权边，则它不应出现在 MST 中。Reverse-Delete 按权重降序删除边，恰好去除了这类冗余边。 复杂度分析 排序边需 \( O(|E| \log |E|) \)。 每次连通性检查（DFS/BFS）需 \( O(|V| + |E|) \)，最多执行 \( |E| \) 次，总复杂度为 \( O(|E| (|V| + |E|)) \)。 优化：使用动态连通性数据结构（如并查集）可优化连通性检查至近似 \( O(|E| \log |V|) \)，但需逆序模拟加边过程（与 Kruskal 类似）。 实例演示 考虑一个 4 顶点图，边权重为： \( (A,B,1), (B,C,2), (C,D,3), (A,D,4) \)。 按权重降序排序边：\( (A,D,4), (C,D,3), (B,C,2), (A,B,1) \)。 尝试删除 \( (A,D,4) \)：删除后图仍连通（通过 \( A \to B \to C \to D \)），故删除。 尝试删除 \( (C,D,3) \)：删除后图仍连通（通过 \( A \to B \to C \) 和 \( A \to D \)），故删除。 尝试删除 \( (B,C,2) \)：删除后图不连通（A、B 与 C、D 分离），故保留。 最后保留边 \( \{ (A,B,1), (B,C,2) \} \)，权重和为 3，即为 MST。