xxx 最小生成树问题（Reverse-Delete 算法） 问题描述 给定一个连通无向图 \( G = (V, E) \)，每条边 \( e \in E \) 有一个权重 \( w(e) \)。目标是找到一个边的子集 \( T \subseteq E \)，使得图 \( G \) 在保留边集 \( T \) 后仍然连通，并且所有边的权重之和 \( \sum_ {e \in T} w(e) \) 最小。这样的子集 \( T \) 称为图 \( G \) 的最小生成树（Minimum Spanning Tree, MST）。 解题过程 Reverse-Delete 算法是求解最小生成树的经典方法之一，其核心思想与 Kruskal 算法相反： Kruskal 算法通过逐步添加当前最小权重的边（且不形成环）来构建 MST。 Reverse-Delete 算法则从原图的所有边出发，逐步删除当前最大权重的边（且不破坏图的连通性），直到剩余边数恰好为 \( |V| - 1 \)。 算法步骤详解 初始化 将原图 \( G \) 的所有边按权重从大到小排序，得到边序列 \( E_ {\text{sorted}} \)。 初始化边集 \( T = E \)，即开始时包含所有边。 遍历边并尝试删除 按权重降序遍历每条边 \( e \in E_ {\text{sorted}} \)： 检查连通性 ：临时从 \( T \) 中移除边 \( e \)，检查图 \( (V, T \setminus \{e\}) \) 是否仍连通。 若图仍连通，说明边 \( e \) 是冗余的（即删除后不影响连通性），则永久删除 \( e \)（令 \( T = T \setminus \{e\} \)）。 若图不再连通，说明边 \( e \) 是必要的（即删除后会破坏连通性），则保留 \( e \) 在 \( T \) 中。 终止条件 当遍历完所有边，或 \( T \) 中边的数量恰好为 \( |V| - 1 \) 时停止。此时 \( T \) 即为最小生成树。 关键点说明 连通性检查 ：通过 DFS 或 BFS 判断图是否连通，时间复杂度为 \( O(|V| + |E|) \)。 正确性保证 ：基于贪心策略，每次删除当前最大权重且不影响连通性的边，最终剩余边集必为 MST（由 MST 的环性质保证：若某边是环中权重最大的边，则它一定不在 MST 中）。 复杂度分析 ： 排序边需 \( O(|E| \log |E|) \)。 最多检查 \( |E| \) 条边，每次连通性检查需 \( O(|V| + |E|) \)，总复杂度为 \( O(|E| (|V| + |E|)) \)。 通过并查集优化可提升效率，但 Reverse-Delete 在实践中的使用不如 Kruskal 或 Prim 算法广泛。 实例演示 考虑一个 4 顶点图，边权重为： \( (A, B, 1) \), \( (B, C, 2) \), \( (C, D, 3) \), \( (D, A, 4) \), \( (A, C, 5) \) 按权重降序遍历边： 检查 \( (A, C, 5) \)：删除后图仍连通，删除。 检查 \( (D, A, 4) \)：删除后图仍连通，删除。 检查 \( (C, D, 3) \)：删除后图不再连通，保留。 检查 \( (B, C, 2) \)：删除后图不再连通，保留。 检查 \( (A, B, 1) \)：删除后图不再连通，保留。 最终 MST 包含边 \( \{ (A,B), (B,C), (C,D) \} \)，总权重为 6。 通过逐步删除冗余边，Reverse-Delete 算法以逆向贪心方式构建出最小生成树。