树的直径求解方法与证明

1. 问题描述

  • 给定一棵树，求树中最长的路径的长度，也就是树的直径；
  • 该树的节点数为 n，编号为0, 1, \cdots, n-1 ；
  • 定义树中某一个节点 v 的相邻节点为 g[v]；

2. 求解方法

  • 从 n 个 节点中随机选择一个节点，假设为 f；
  • 在树中找一条以 f 为起点的最长路径；该方法可以用深度优先搜索的方法做（详细描述见下文[4]）；
  • 假设找到的路径的另外一个端点为 s，那么树中以 s 为起点的最长的路径的长度便是树的直径

3. 证明

假设一颗树如下图所示：


树

再假设，第一个节点选择的是 节点 1，以 节点1 为起点的最长的路径是 1 \to 2 \to 3 \to 4 \to \cdots \to 6 。基于上述假设，要证明上述方法正确，即证明：

  • 节点1 或 6 是某条最长路径的一个端点。

要证明上述结论，假设某一个节点 u 是树中某一个最长路径的端点，该路径为 l，有如下结论：

  • 节点 u 不是 2 \to 3 \to \cdots 中的一个（不包括节点 6）：如果是，那么肯定存在更长的一条路径；
  • l 与 1 \to 2 \to \cdots \to 6 重叠一边，且重叠部分为靠近 节点6 的那边，证明方法为：
    • 如果 l 与 1 \to 2 \to \cdots \to 6 完全不相交，那么 l 可能是 7 \to \cdots \to 5 \to \cdots \to 8 这种路径，此时可以找到比 l 更长的路径。
    • 如果 l 与 1 \to 2 \to \cdots \to 6 相交于某一个节点，此时也可以找到比 l 更长的路径。

上述例子可以扩展成一般的情况。因此，上述结论成立，从而上述方法正确。

4. 给定某一个节点求解树中离这个节点最远的节点以及对应路径长度

使用DFS可以解决这个问题。

定义 dfs(v) 的含义为，返回范围以 节点 v 为根的子树中距离最远的节点以及对应的长度。

def dfs(v):
  max_dis = 0
  max_node = v
  for u in child(v):
    update_node, update_dis = dfs(u) + 1
    if update > max_dis:
      max_dis = update_dis
      max_node = update_node
  return max_node, max_dis

通过上述递归的方法就可以求出对应的节点，以及具体的距离。

©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容