1. 問(wèn)題描述

• 給定一棵樹(shù)，求樹(shù)中最長(zhǎng)的路徑的長(zhǎng)度，也就是樹(shù)的直徑；
• 該樹(shù)的節(jié)點(diǎn)數(shù)為 ，編號(hào)為 ；
• 定義樹(shù)中某一個(gè)節(jié)點(diǎn) 的相鄰節(jié)點(diǎn)為 ；

2. 求解方法

• 從 個(gè) 節(jié)點(diǎn)中隨機(jī)選擇一個(gè)節(jié)點(diǎn)，假設(shè)為 ；
• 在樹(shù)中找一條以 為起點(diǎn)的最長(zhǎng)路徑；該方法可以用深度優(yōu)先搜索的方法做（詳細(xì)描述見(jiàn)下文[4]）；
• 假設(shè)找到的路徑的另外一個(gè)端點(diǎn)為 ，那么樹(shù)中以 為起點(diǎn)的最長(zhǎng)的路徑的長(zhǎng)度便是樹(shù)的直徑

3. 證明

假設(shè)一顆樹(shù)如下圖所示：

樹(shù)

再假設(shè)，第一個(gè)節(jié)點(diǎn)選擇的是 節(jié)點(diǎn) ，以 節(jié)點(diǎn) 為起點(diǎn)的最長(zhǎng)的路徑是 。基于上述假設(shè)，要證明上述方法正確，即證明：

• 節(jié)點(diǎn) 或 是某條最長(zhǎng)路徑的一個(gè)端點(diǎn)。

要證明上述結(jié)論，假設(shè)某一個(gè)節(jié)點(diǎn) 是樹(shù)中某一個(gè)最長(zhǎng)路徑的端點(diǎn)，該路徑為 ，有如下結(jié)論：

• 節(jié)點(diǎn) 不是 中的一個(gè)（不包括節(jié)點(diǎn) ）：如果是，那么肯定存在更長(zhǎng)的一條路徑；
• 與 重疊一邊，且重疊部分為靠近 節(jié)點(diǎn) 的那邊，證明方法為：
  • 如果 與 完全不相交，那么 可能是 這種路徑，此時(shí)可以找到比 更長(zhǎng)的路徑。
  • 如果 與 相交于某一個(gè)節(jié)點(diǎn)，此時(shí)也可以找到比 更長(zhǎng)的路徑。

上述例子可以擴(kuò)展成一般的情況。因此，上述結(jié)論成立，從而上述方法正確。

4. 給定某一個(gè)節(jié)點(diǎn)求解樹(shù)中離這個(gè)節(jié)點(diǎn)最遠(yuǎn)的節(jié)點(diǎn)以及對(duì)應(yīng)路徑長(zhǎng)度

使用DFS可以解決這個(gè)問(wèn)題。

定義 dfs(v) 的含義為，返回范圍以 節(jié)點(diǎn) 為根的子樹(shù)中距離最遠(yuǎn)的節(jié)點(diǎn)以及對(duì)應(yīng)的長(zhǎng)度。

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

通過(guò)上述遞歸的方法就可以求出對(duì)應(yīng)的節(jié)點(diǎn)，以及具體的距離。