如果真要暴力枚举每一棵生成树再求半径逻辑上完全可行但复杂度是指数级的Cayley公式n个点有 nn−2nn−2 棵。不过纯为了理解算法我们可以分两步走第一步暴力枚举出所有生成树DFS回溯对于n 个点m 条边的无向图选边法回溯对每一条边决策“选”或“不选”。并查集判环如果选择一条边后两个端点已经在同一集合会成环则剪枝跳过。终止条件当选中的边数达到 n−1n−1 条时说明形成了一棵生成树马上拿去算半径。伪代码逻辑textdfs(当前边下标idx, 已选边数cnt): if cnt n-1: 计算当前选中集合的半径更新全局最小值 return if idx m: return // 剪枝剩余边全选也不够 n-1 条时直接返回 if (m - idx) (n-1 - cnt): return // 不选当前边 dfs(idx1, cnt) // 选当前边 (需判环) if find(u) ! find(v): 合并 u,v 记录这条边 dfs(idx1, cnt1) 撤销合并(回溯)第二步计算给定生成树的半径拿到 n−1n−1 条边后有多种方式算半径树的半径 直径长度的一半向上取整暴力 BFS/DFS对每个点跑一次遍历记录离它最远的距离离心率取所有点离心率的最小值。复杂度 O(n2)O(n2)。更高效先两次 DFS 找树的直径最远两点距离 DD半径就是 ⌈D/2⌉⌈D/2⌉。因为树是唯一的路径中心一定在直径上。针对你给的例子1-2, 2-3, 1-3, 3-4暴力回溯会枚举 3 种合法组合去掉三角形的一条边组合① (1-3,2-3,3-4)直径2半径1组合② (1-2,2-3,3-4)直径2半径1组合③ (1-2,1-3,3-4)直径3半径2最终取最小值min(1,1,2) 1。这种暴力的极限适合n ≤ 10左右生成树数量可控。如果n15最多 15131513 棵树宇宙毁灭都算不完这时候就只能用我们之前说的“中心最短路树”定理秒杀了。