xxx 最小高度生成树问题 题目描述 ： 给定一个连通无向图G=(V,E)，其中V是顶点集，E是边集。图可能带有边权（可以视为无权重，即所有权重为1）。生成树T是G的一个子图，包含所有顶点且是树结构（无环连通）。树的高度定义为从任意选定的根节点到最远叶节点的路径长度（边数）。最小高度生成树问题要求找到G的一棵生成树，使得其高度最小。 解题过程 ： 1. 问题理解 目标不是最小化总边权（如最小生成树），而是最小化树的高度。 高度取决于根节点的选择：同一棵树选择不同根节点，高度可能不同。 需要同时确定根节点和树结构，使高度最小。 2. 关键观察 最小高度生成树的根必须是图的"中心"顶点（离心率最小的顶点）。 图的偏心率：顶点v的偏心率为所有其他顶点到v的最短距离的最大值。 图半径：最小偏心率。图直径：最大偏心率。 最小高度生成树的高度等于图半径。 3. 算法思路 步骤1：找到图的所有中心顶点（偏心率等于半径的顶点）。 步骤2：以任意中心顶点为根，用BFS方式构建生成树。 4. 具体步骤 步骤1：计算所有顶点对最短路径 使用Floyd-Warshall算法或多次BFS（无权图）计算距离矩阵dist。 Floyd-Warshall算法： 初始化dist矩阵，对角线为0，有边为权（无权图为1），无边为∞。 对每个中间顶点k，遍历所有顶点对(i,j)，更新dist[ i][ j] = min(dist[ i][ j], dist[ i][ k] + dist[ k][ j ])。 步骤2：计算每个顶点的偏心率和半径 对每个顶点v，偏心率ecc(v) = max{ dist[ v][ u ] for all u ∈ V }。 图半径radius = min{ ecc(v) for all v ∈ V }。 记录所有满足ecc(v) == radius的顶点作为中心顶点集合C。 步骤3：构建最小高度生成树 从任意中心顶点r ∈ C开始进行BFS： 初始化队列，将r入队，标记距离为0。 维护数组parent记录每个顶点的父节点（树中的前驱）。 遍历时，对于顶点u的每个未访问邻居v，设置parent[ v ] = u，并加入队列。 BFS树即为最小高度生成树，高度等于radius。 5. 算法正确性 BFS树保证连通且无环（每个非根节点只有一个父节点）。 以中心顶点为根，BFS树的高度恰好等于半径，是最小可能高度。 证明：任意生成树高度至少为半径（根到最远叶子的距离≥根的偏心率≥半径）。 6. 复杂度分析 Floyd-Warshall：O(|V|³)，BFS建树：O(|V|+|E|)。 总体复杂度O(|V|³)，适合|V|不大的图。对于无权图，可用|V|次BFS（O(|V|(|V|+|E|))）替代Floyd-Warshall。 7. 示例 考虑5个顶点的环图：顶点A-B-C-D-E-A（无权）。 距离矩阵：相邻距离1，相隔两个顶点距离2，等。 偏心率：每个顶点ecc=2（到最远顶点距离2），半径=2。 中心顶点：所有顶点（环图的每个顶点都是中心）。 以A为根BFS：A连接B和E，B连接C，E连接D，高度为2。