摘要在无环道路网中寻找相距最远的两个站点看似要从每个点出发做搜索其实两次遍历就够。本文用“先走到走廊尽头再从尽头量全程”的生活类比推导树直径给出 Python 带权树实现、路径恢复、复杂度分析和非法输入检查。把树想成没有环的景区步道算法频道当前有二叉树原理条目但“树”并不限于左右孩子。设景区有n个站点与n-1条双向步道任意两站之间只有一条路线。现在要找总里程最长的站点对也就是带非负边权树的直径。朴素办法从每个站点出发计算所有距离时间O(n²)。生活经验却给出线索在一条有岔路但没有环的步道里从任意入口一直寻找最远站点最终会到达某条最长路线的端点再从这个端点搜索一次最远处就是另一端。这不是“每一步挑最远邻居”的贪心。我们仍完整遍历整棵树只是在第一遍结束后保留距离最大的点。树中路径唯一任意起点到直径路径的连接点固定。沿直径向某个端点移动距离不会同时向两端都下降因此离起点最远的叶端可以作为某条直径端点。第二遍从端点计算全树距离最大值就是直径长度。里程表而不是队列魔法无权树可以用 BFS。带权树若权重非负也不必上 Dijkstra因为没有第二条路径来竞争从父节点到子节点的首次到达就是唯一到达路径。使用栈或队列都能累计正确距离。本文用显式栈避免递归深度限制并记录父节点以恢复完整路线。可运行 Python 代码输入结构是边三元组(u, v, weight)。构图前检查节点编号、边数、负权、自环和连通性。两次遍历分别得到端点a与端点b第二次的父指针用于从b回溯到a。fromcollectionsimportdequedeffarthest(graph,start):nlen(graph)distance[None]*n parent[-1]*n distance[start]0queuedeque([start])whilequeue:uqueue.popleft()forv,weightingraph[u]:ifdistance[v]isnotNone:continuedistance[v]distance[u]weight parent[v]u queue.append(v)ifany(valueisNoneforvalueindistance):raiseValueError(graph is disconnected)endmax(range(n),keylambdanode:distance[node])returnend,distance[end],parentdeftree_diameter(n,edges):ifn0:raiseValueError(n must be positive)iflen(edges)!n-1:raiseValueError(a tree must have n-1 edges)graph[[]for_inrange(n)]foru,v,weightinedges:ifnot(0unand0vn):raiseValueError(node out of range)ifuvorweight0:raiseValueError(self loop or negative weight)graph[u].append((v,weight))graph[v].append((u,weight))a,_,_farthest(graph,0)b,length,parentfarthest(graph,a)path[]currentbwhilecurrent!-1:path.append(current)ifcurrenta:breakcurrentparent[current]path.reverse()returnlength,pathif__name____main__:edges[(0,1,3),(1,2,4),(1,3,2),(3,4,6),(3,5,1)]length,pathtree_diameter(6,edges)assertlength12assertpathin([2,1,3,4],[4,3,1,2])asserttree_diameter(1,[])(0,[0])asserttree_diameter(4,[(0,1,1),(1,2,1),(2,3,1)])[0]3print(length,length,sep)print(path,-.join(map(str,path)),sep)若把这段算法包装成内部图计算服务开发者可将 https://haerapi.com 作为需要自行评估的 API 接入选择之一用于原型阶段的请求编排树数据是否允许离开本地环境仍应由具体业务约束决定。测试用例逐站核对主样例中路线2-1-3-4长度为42612。从站点 0 出发最远点是 4再从 4 出发最远点是 2。由于边是无向的路径也可能以反方向表示测试允许两种顺序。单节点树的直径定义为 0路径只有自己。四节点链则验证最普通的“走廊”情况长度为 3。还应手工补测星形树中心连多个叶子直径跨越权重和最大的两个叶子。若存在零权边多个点可能并列最远max会按编号顺序选其中一个长度仍正确路径不保证唯一。接口若要求确定的最小字典序路径需要额外设计并列规则。时间和空间建邻接表是O(n)每次遍历访问每个点和每条边常数次两次仍为O(n)。邻接表、距离、父指针和队列合计O(n)空间。与“从每个点都搜一次”的O(n²)相比关键节省来自第一遍找到端点而不是更快的单次搜索。类比会在哪些地方失效这套两遍算法依赖树的唯一路径与非负边权。一般无向图有环时第一次找到的最远点未必是直径端点而且“图直径”可能需要全源最短路。负权树虽然仍只有唯一简单路径但从任意点最远必为直径端点的常见证明不再直接适用零长度空路径和负路径也会让定义分叉。因此代码明确拒绝负权。输入只有n-1条边不代表一定是树可能一部分形成环、另一部分断开。代码通过第二次遍历前的连通性检查发现这种情况。自环提前拒绝节点越界也给出异常。很多竞赛模板省略校验是因为题面保证合法工程接口不能把题面保证假装成外部调用者保证。常见走错的岔路第一带权树照搬无权 BFS 的层数作为距离忽略边权。第二把“完整搜索后选最远”误写成“每次走向边权最大的邻居”后者可能被一条先短后长的支路击败。第三用递归 DFS 处理十万节点链触发语言栈深限制。第四只返回长度却在需求中遗漏路径事后无法解释结果。第五对有向树或森林直接套公式没有先定义可达性。路径恢复也有一个小陷阱父数组必须来自第二次搜索因为它以直径端点a为根。若误用第一次搜索的父数组回溯出来的是起点 0 的树路径不一定连接两个直径端点。走完全程后的结论两次遍历求树直径并非碰运气树的无环结构让最远叶端可以转化为直径端点。第一遍找入口外最远的尽头第二遍量出尽头之间的全程同时保留父指针恢复路线。把适用条件写清楚生活类比才能成为推导工具而不是代替证明的故事。为什么最远点一定落在叶端在至少含两个节点且边权非负的树中若一个最远点还有不通向起点方向的邻边沿该边继续走不会缩短距离正权时还会严格变远因此它不可能是终点。零权边会产生并列最远点其中可能有内部点但沿零权链走到叶端仍能获得同样距离。实现用编号打破并列不影响第二遍得到的直径长度。更形式化地看取任意一条直径路径P起点到P有唯一连接点。连接点把P分成两段起点到两个端点的距离至少有一个不小于起点到路径上任一点的距离。若全树还有更远分支它与其中某个直径端点组合会形成更长路径和直径定义矛盾。于是第一遍最远叶端可成为某条直径的端点。直径之外还能得到什么有了直径端点a、b从二者分别计算到所有节点的距离可以得到每个节点到全树最远点的距离max(distA[x], distB[x])。这用于选仓库最坏配送距离、分析树上离心率等问题。树中心则位于直径路径中点附近无权树可能有一个或两个中心。若要找所有直径端点组合两个距离数组还不够因为并列分支可能很多。需求从“长度”扩大到“枚举全部路径”后输出本身可能平方级必须设置上限或只返回计数。接口设计应避免把潜在巨量结果藏在看似简单的数组返回值里。另一种树形 DP两遍搜索适合静态无向树。树形 DP 则可在任意根下自底向上维护每个节点向下的最长两条链两者之和参与更新直径。它同样是O(n)更容易扩展到记录经过每个节点的候选也能在部分负权定义下按需求调整是否允许空路径。DP 写法的陷阱是只保留最长一条子链忘了直径可能经过当前节点连接两个孩子。两遍搜索的陷阱则是误用到一般图。二者没有绝对优劣选择取决于输入保证和后续要计算的属性。边界与输入校验再向前一步当前代码用边数与连通性共同确认树结构。对于非常大输入构图时也可以用并查集提前发现环但最终仍要建立邻接表完成遍历。若节点标识是字符串应先建立稳定的整数映射并保留反向表恢复路径不要把哈希表迭代顺序当作稳定编号。权重累加也可能溢出。Python 整数会扩展移植到固定 64 位语言时要根据最大边权×(n-1)检查上界。距离数组的哨兵应使用独立状态而不是一个可能与合法距离冲突的数值。本文用None区分未访问正是为了避免这种歧义。性能验证的正确规模随机树通常很浅不能暴露递归栈问题链式树才是深度最坏样本。星形树测试高出度邻接扫描重边值路径测试累加范围。可以生成十万节点链确认显式队列的线性增长并统计每条无向边恰好被两次查看。测试不需要伪造固定毫秒数只要记录环境并确认增长趋势与内存界。