xxx 最小高度生成树问题 题目描述 给定一个连通无向图 \( G = (V, E) \)，每条边没有权重。目标是找到一个生成树 \( T \)，使得树的高度最小。树的高度定义为从根节点到最远叶节点的最长路径上的边数。换句话说，我们需要在图中选择一个根节点，并构造一棵生成树，使得根到所有叶节点的最大距离尽可能小。这个问题在实际中常用于网络设计、分布式系统主节点选举等场景，要求中心节点到所有其他节点的跳数尽量少。 解题思路 最小高度生成树问题可以通过图的 广度优先搜索（BFS） 性质解决。核心观察是：若以图中任意一个 最小偏心距顶点（即图的中心） 为根进行BFS，得到的BFS树的高度最小。图的偏心距（eccentricity）定义为顶点到图中其他顶点的最大最短距离，而半径（radius）是所有偏心距的最小值。最小高度生成树的高度等于图的半径。因此，解题步骤分为两步： 找到图的所有顶点对最短路径（APSP），确定每个顶点的偏心距和图的半径。 选择偏心距等于半径的顶点作为根，通过BFS构建生成树。 详细步骤 步骤1: 计算所有顶点对最短路径 由于图是无权图，可以使用BFS从每个顶点出发计算单源最短路径。 具体操作：对每个顶点 \( v \in V \)，执行BFS遍历图，记录 \( v \) 到其他所有顶点的距离 \( dist(v, u) \)。 时间复杂度：每个顶点BFS需 \( O(|V| + |E|) \)，总复杂度为 \( O(|V|(|V| + |E|)) \)。若使用邻接表，通常为 \( O(|V|^2) \) 对于稠密图。 步骤2: 计算每个顶点的偏心距和图的半径 对于顶点 \( v \)，其偏心距 \( ecc(v) = \max_ {u \in V} dist(v, u) \)。 遍历所有顶点后，图的半径 \( rad(G) = \min_ {v \in V} ecc(v) \)。 同时记录所有满足 \( ecc(v) = rad(G) \) 的顶点，这些顶点是候选根节点。 步骤3: 构建最小高度生成树 从任意一个候选根节点 \( r \)（偏心距等于半径）开始，执行BFS遍历。 BFS过程中，记录每个节点的父节点，形成一棵树。BFS树天然保证根到任意节点的距离等于最短路径，因此树的高度恰好为 \( ecc(r) = rad(G) \)，即最小可能高度。 注意：BFS树是生成树，因为BFS会访问所有顶点，且无环。 示例演示 考虑一个简单图：顶点集 \( V = \{A, B, C, D\} \)，边集 \( E = \{(A,B), (B,C), (C,D), (A,D)\} \)（形成一个四边形加一条对角线）。 计算APSP： BFS从A出发：dist(A,A)=0, dist(A,B)=1, dist(A,D)=1, dist(A,C)=2（路径A-D-C）。 类似计算其他顶点，得到偏心距： \( ecc(A) = \max(0,1,1,2) = 2 \) \( ecc(B) = 2 \), \( ecc(C) = 2 \), \( ecc(D) = 2 \)（所有顶点偏心距均为2）。 半径 \( rad(G) = 2 \)。 选择根节点（如A），执行BFS：访问顺序 A → B, D → C。树边为 A-B, A-D, D-C，高度为2。 复杂度分析 时间主导步骤是APSP计算：\( O(|V|(|V| + |E|)) \)。 空间复杂度：存储距离矩阵需 \( O(|V|^2) \)，但可优化为每次BFS后只保留偏心距。 关键点总结 最小高度生成树的高度等于图的半径。 BFS是核心工具，既用于计算最短路径，也用于构建树。 对于加权图，问题变为NP难，需使用近似算法（如基于最小直径生成树的方法）。