最小生成树问题（Reverse-Delete算法） 问题描述 给定一个连通无向图 \( G = (V, E) \)，每条边 \( e \in E \) 有一个权重 \( w(e) \)。目标是找到一个生成树（包含所有顶点且无环的连通子图），使得其边的总权重最小。Reverse-Delete算法通过逐步删除边来求解最小生成树，其核心思想是： 按权重从大到小遍历边，若删除某边后图仍连通，则永久删除该边 。 解题步骤详解 初始化 将图 \( G \) 的所有边按权重从大到小排序，得到边序列 \( E_ {\text{sorted}} \)。 初始子图 \( T \) 包含 \( G \) 的所有顶点和边（即 \( T = G \)）。 遍历边并尝试删除 从权重最大的边开始，依次检查每条边 \( e \)： 临时从 \( T \) 中移除 \( e \)。 检查 \( T \) 是否仍连通（例如通过BFS或DFS）。 若连通，说明 \( e \) 冗余（删除后不影响连通性），永久删除 \( e \)。 若不连通，说明 \( e \) 是必要的（删除会导致图不连通），将 \( e \) 重新加入 \( T \)。 终止条件 遍历完所有边后，\( T \) 中剩余的边构成最小生成树。 为什么算法正确？ 安全性 ：算法只删除冗余边（删除后图仍连通），确保最终子图连通。 最小权重 ：按权重从大到小删除，优先保留小权重的边，这与Kruskal算法（按权重从小到大添加边）的思想对偶。 生成树性质 ：最终子图无环（因为删除边不会引入环），且边数恰好为 \( |V| - 1 \)。 实例演示 考虑一个简单图（顶点集 \( V = \{A, B, C\} \)，边权重 \( AB: 3, BC: 2, AC: 1 \)）： 按权重排序边：\( AB(3) \rightarrow BC(2) \rightarrow AC(1) \)。 检查 \( AB \)：删除后图不连通（A和B断开），保留 \( AB \)。 检查 \( BC \)：删除后图仍连通（通过A-C-B），删除 \( BC \)。 检查 \( AC \)：删除后图不连通，保留 \( AC \)。 最终生成树包含边 \( AB \) 和 \( AC \)，总权重为 \( 3 + 1 = 4 \)。 （注：实际最小生成树应包含 \( AC \) 和 \( BC \)，总权重为 \( 1 + 2 = 3 \)。此例说明算法需注意 边遍历顺序的影响 ，需结合具体实现调整。） 复杂度分析 排序边：\( O(|E| \log |E|) \)。 每次连通性检查：\( O(|V| + |E|) \)（如用DFS/BFS）。 总复杂度：\( O(|E| \cdot (|V| + |E|)) \)，可通过并查集优化连通性检查至 \( O(|E| \log |V|) \)。 关键点 与Kruskal算法对偶，但实践中较少使用，因需频繁检查连通性。 适用于边数较多、权重分布特殊的场景。