树的直径：概念、算法与应用详解

1. 什么是树的直径在树形数据结构中树的直径Tree Diameter定义为树中任意两个节点之间的最长路径长度。这条最长路径可能经过根节点也可能不经过。直径的长度通常用路径上的边数无权图或边的权重之和带权图来衡量。例如对于一棵有 n 个节点的树其直径的取值范围是 [1, n-1]。当树退化成一条链时直径达到最大值 n-1当树为星形结构一个中心节点连接所有其他节点时直径最小为 2。2. 求解树的直径的经典算法2.1 两次 DFS/BFS 法最常用这是求解无权树直径最经典、最高效的算法时间复杂度为 O(n)只需两次遍历从任意节点通常选节点 1出发进行 DFS 或 BFS找到距离最远的节点 u。从节点 u 出发再次进行 DFS 或 BFS找到距离 u 最远的节点 v。节点 u 和 v 之间的路径就是树的一条直径其长度即为直径值。算法正确性证明第一次遍历找到的 u 一定是某条直径的端点。第二次遍历从 u 出发找到的 v 就是直径的另一个端点。2.2 树形 DP 法通过一次 DFS 同时计算每个节点的“向下最长路径”和“次长路径”动态维护直径// C 示例代码 #include iostream #include vector #include algorithm using namespace std; vectorvectorint adj; int diameter 0; int dfs(int u, int parent) { int max1 0, max2 0; // 最长和次长向下路径 for (int v : adj[u]) { if (v parent) continue; int depth dfs(v, u) 1; if (depth max1) { max2 max1; max1 depth; } else if (depth max2) { max2 depth; } } diameter max(diameter, max1 max2); return max1; } int main() { int n 7; adj.resize(n 1); // 构建树: 1-2, 1-3, 2-4, 2-5, 3-6, 3-7 adj[1].push_back(2); adj[2].push_back(1); adj[1].push_back(3); adj[3].push_back(1); adj[2].push_back(4); adj[4].push_back(2); adj[2].push_back(5); adj[5].push_back(2); adj[3].push_back(6); adj[6].push_back(3); adj[3].push_back(7); adj[7].push_back(3); dfs(1, 0); cout lt;lt; 树的直径: lt;lt; diameter lt;lt; endl; // 输出 4 return 0; }3. 带权树的直径当树的边带有权重时直径定义为路径上所有边权重之和的最大值。求解方法同样可以使用两次 DFS/BFS 或树形 DP只需在计算距离时累加权重即可。# Python 示例带权树的直径两次DFS from collections import defaultdict def dfs(start, n, graph): 返回 (最远节点, 最大距离) stack [(start, -1, 0)] # (当前节点, 父节点, 累计距离) max_dist 0 farthest start while stack: u, parent, dist stack.pop() if dist max_dist: max_dist dist farthest u for v, w in graph[u]: if v ! parent: stack.append((v, u, dist w)) return farthest, max_dist def tree_diameter_weighted(n, edges): n个节点edges: [(u, v, w), ...] graph defaultdict(list) for u, v, w in edges: graph[u].append((v, w)) graph[v].append((u, w)) # 第一次DFS endpoint1, _ dfs(1, n, graph) # 第二次DFS endpoint2, diameter dfs(endpoint1, n, graph) return diameter, endpoint1, endpoint2 示例带权树 n 5 edges [(1, 2, 3), (2, 3, 5), (2, 4, 1), (1, 5, 2)] diameter, u, v tree_diameter_weighted(n, edges) print(f直径端点: {u} 和 {v}, 直径长度: {diameter}) # 输出 84. 直径的性质与应用4.1 重要性质直径不一定唯一一棵树可能有多个直径但它们的长度相同。所有直径相交于中心树的所有直径都经过树的中心一个节点或一条边。直径的端点一定是叶子节点度数为 1 的节点。树的中心直径的中点称为树的中心可用于优化树上的操作。4.2 实际应用场景网络设计在通信网络中树的直径反映了最坏情况下的传输延迟。社交网络分析树形结构的组织或传播网络中直径表示信息传播的最长路径。算法竞赛许多树形 DP 问题需要计算直径或利用直径性质优化。数据结构优化以树的中心为根重建树可以使树的高度最小化优化查询效率。5. 常见变体与扩展5.1 动态树的直径支持添加/删除边操作动态维护树的直径。可以使用 LCTLink-Cut Tree或树的直径性质结合并查集解决。5.2 所有直径端点找出树的所有直径端点。可以通过两次 DFS 找到一条直径后检查其他叶子节点是否也能构成相同长度的路径。5.3 直径上的节点给定一棵树快速判断某个节点是否在直径上。可以通过计算该节点到两个直径端点的距离之和是否等于直径长度来判断。6. 总结树的直径是树形结构中的一个基础且重要的概念。掌握两次 DFS/BFS 和树形 DP 这两种求解方法理解直径的性质能够帮助解决许多树相关的算法问题。在实际应用中根据是否需要处理带权边、动态修改等需求选择合适的算法变体。