尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
树的直径:概念、算法与应用详解
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 这两种求解方法理解直径的性质能够帮助解决许多树相关的算法问题。在实际应用中根据是否需要处理带权边、动态修改等需求选择合适的算法变体。
RELATED

相关推荐

DAY X项目日志系统:从开发到CI/CD的全流程实践

DAY X项目日志系统:从开发到CI/CD的全流程实践

1. 项目概述"DAY 15"这个看似简单的标题背后,实际上蕴含着丰富的可能性。作为一个开放式的项目命名,它可能指向多种场景:可能是某个30天挑战的第15天记录,可能是某个开发项目的里程碑节点,也可能是某个实验或…

📅 2026/10/7 8:53:43
AI赋能远程控制:8款智能方案对比与实战部署指南

AI赋能远程控制:8款智能方案对比与实战部署指南

远程控制软件,一个听起来有点“古典”的领域,似乎和AI、大模型这些前沿技术关系不大。但如果你还停留在“远程控制就是连个桌面、传个文件”的认知,那可能就错过了2026年最值得关注的效率革命。当大模型的能力开始渗透到远程控制的每一个环节…

📅 2026/10/17 20:50:23
AIGC率怎么降?2026年实测:从55%降到9%的6个有效方法

AIGC率怎么降?2026年实测:从55%降到9%的6个有效方法

室友的毕业论文初稿被退回了,理由只有一行字:AIGC率55%,请修改后重新提交。他整个人都懵了——查重率明明只有9%,怎么AI率会超标这么多?2026年的毕业季,类似的情况在各高校轮番上演,AI率已经成了…

📅 2026/9/19 10:23:03
MORE NEWS

更多资讯

📰

国内电工证香港能用吗网上查询报名全攻略

国内电工证香港能用吗网上查询报名全攻略 学历不高怕报不上名?想知道自己手里的国内电工证能不能在 香港 使用?别急,这篇讲清楚, 网上查询 也简单,报考流程、证书使用范围、怎么避坑都给你安排上,全是实打实的干货。…

📰

电工证交给公司合同值不值得考?怕考不过白交培训费的别错过

电工证交给公司合同值不值得考?怕考不过白交培训费的别错过 怕考不过白交培训费?现在不少电工朋友在考虑报考电工证时,最怕的就是花钱又没用,尤其是当公司要求你把电工证交给公司合同,心里更没底。你是不是也在纠结,电工证到底值不值得考?这篇文章就帮…

📰

在保山考电工证报名流程全公开 3天搞定网上查询方法

在保山考电工证报名流程全公开 3天搞定网上查询方法 你还在为找不到电工证报名入口发愁?别让没证耽误你找工作,今天教你 在保山考电工证 的全流程,轻松 网上查询 ,3天搞定报名!电工证不仅是上岗的“入场券”,更是你收入翻倍的关键一步。…

📰

电工证被盗用怎么查 你的证在外省考的能转过来吗

电工证被盗用怎么查 你的证在外省考的能转过来吗 之前考的证在外省能不能转过来,这事儿不少人都在问,特别是像你这样在漯河的中小施工企业负责人,经常需要跨省接项目,证照问题成了心头病。如果你的电工证被人盗用,又不知道怎么查,那就更糟心了。今天就…

📰

低压电工证全部题目内部消息:三门峡应届生避坑全攻略

低压电工证全部题目内部消息:三门峡应届生避坑全攻略 你是不是也在找低压电工证全部题目?又怕被中介骗钱?这年头,考个证都得擦亮眼睛,别让那些打着“内部消息”旗号的骗子把你的钱和时间都骗走。…

📰

湘西电工证在哪报名多久拿证?外省证转过来怎么操作

湘西电工证在哪报名多久拿证?外省证转过来怎么操作 之前考的证在外省能不能转过来?很多在湘西的电工朋友都问过这个问题,特别是那些从外地转过来的,或者是已经在其他城市考过电工证的朋友。好消息是,…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬