咨询边带权无向树的最长路径求解算法方案

核心算法步骤 #

• 第一步：任选树中一个节点，通过带权DFS或带权BFS遍历整棵树，找到距离该节点最远的节点，记为u
• 第二步：从节点u出发，再次执行带权遍历，找到距离u最远的节点v，u到v的路径即为树的最长路径（树的直径）

算法原理 #

树的最长路径（直径）的两个端点必然是树的叶节点。第一次遍历找到的最远节点u，一定是直径的其中一个端点；第二次从u出发找到的最远节点v，就是直径的另一个端点，二者之间的路径自然是整棵树的最长路径。

实现细节 #

• 带权遍历的核心是：遍历过程中累计经过边的权重，而非单纯统计节点数量
• 遍历过程中标记父节点，避免回溯到上一个节点（因为树无环连通，无需额外的访问标记数组，父节点标记足够）
• 如果需要输出具体路径，可在遍历过程中记录每个节点的前驱节点，找到v后反向回溯即可得到完整路径

对您提到的算法的补充说明 #

• 普通BFS/DFS并非不适用，只是您需要使用带权版本的实现——把原本统计节点步数的逻辑，改成累加边的权重即可
• MST算法确实与该问题无关，因为输入本身就是一棵无环连通树，无需再构建最小生成树

内容的提问来源于stack exchange，提问作者yowiee