跳转至

樹的直徑

樹上任意兩節點之間最長的簡單路徑即為樹的「直徑」。

前置知識：樹基礎。

引入

顯然，一棵樹可以有多條直徑，他們的長度相等。

可以用兩次 DFS 或者樹形 DP 的方法在 \(O(n)\) 時間求出樹的直徑。

例題

SPOJ PT07Z, Longest path in a tree

給定一棵 \(n\) 個節點的樹，求其直徑的長度。\(1\leq n\leq 10^4\)。

做法 1. 兩次 DFS

過程

首先從任意節點 \(y\) 開始進行第一次 DFS，到達距離其最遠的節點，記為 \(z\)，然後再從 \(z\) 開始做第二次 DFS，到達距離 \(z\) 最遠的節點，記為 \(z'\)，則 \(\delta(z,z')\) 即為樹的直徑。

顯然，如果第一次 DFS 到達的節點 \(z\) 是直徑的一端，那麼第二次 DFS 到達的節點 \(z'\) 一定是直徑的一端。我們只需證明在任意情況下，\(z\) 必為直徑的一端。

定理：在一棵樹上，從任意節點 \(y\) 開始進行一次 DFS，到達的距離其最遠的節點 \(z\) 必為直徑的一端。

證明

使用反證法。記出發節點為 \(y\)。設真實的直徑是 \(\delta(s,t)\)，而從 \(y\) 進行的第一次 DFS 到達的距離其最遠的節點 \(z\) 不為 \(t\) 或 \(s\)。共分三種情況：

  • 若 \(y\) 在 \(\delta(s,t)\) 上：

y 在 s-t 上

有 \(\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)\)，與 \(\delta(s,t)\) 為樹上任意兩節點之間最長的簡單路徑矛盾。

  • 若 \(y\) 不在 \(\delta(s,t)\) 上，且 \(\delta(y,z)\) 與 \(\delta(s,t)\) 存在重合路徑：

y 不在 s-t 上，y-z 與 s-t 存在重合路徑

有 \(\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)\)，與 \(\delta(s,t)\) 為樹上任意兩節點之間最長的簡單路徑矛盾。

  • 若 \(y\) 不在 \(\delta(s,t)\) 上，且 \(\delta(y,z)\) 與 \(\delta(s,t)\) 不存在重合路徑：

y 不在 s-t 上，y-z 與 s-t 不存在重合路徑

有 \(\delta(y,z) > \delta(y,t) \Longrightarrow \delta(x',z) > \delta(x',t) \Longrightarrow \delta(x,z) > \delta(x,t) \Longrightarrow \delta(s,z) > \delta(s,t)\)，與 \(\delta(s,t)\) 為樹上任意兩節點之間最長的簡單路徑矛盾。

綜上，三種情況下假設均會產生矛盾，故原定理得證。

負權邊

上述證明過程建立在所有路徑均不為負的前提下。如果樹上存在負權邊，則上述證明不成立。故若存在負權邊，則無法使用兩次 DFS 的方式求解直徑。

實現

代碼實現如下。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N = 10000 + 10;

int n, c, d[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    d[v] = d[u] + 1;
    if (d[v] > d[c]) c = v;
    dfs(v, u);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  d[c] = 0, dfs(c, 0);
  printf("%d\n", d[c]);
  return 0;
}

如果需要求出一條直徑上所有的節點，則可以在第二次 DFS 的過程中，記錄每個點的前序節點，即可從直徑的一端一路向前，遍歷直徑上所有的節點。

做法 2. 樹形 DP

過程 1

我們記錄當 \(1\) 為樹的根時，每個節點作為子樹的根向下，所能延伸的最長路徑長度 \(d_1\) 與次長路徑（與最長路徑無公共邊）長度 \(d_2\)，那麼直徑就是對於每一個點，該點 \(d_1 + d_2\) 能取到的值中的最大值。

樹形 DP 可以在存在負權邊的情況下求解出樹的直徑。

實現 1

代碼實現如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
const int N = 10000 + 10;

int n, d = 0;
int d1[N], d2[N];
vector<int> E[N];

void dfs(int u, int fa) {
  d1[u] = d2[u] = 0;
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    int t = d1[v] + 1;
    if (t > d1[u])
      d2[u] = d1[u], d1[u] = t;
    else if (t > d2[u])
      d2[u] = t;
  }
  d = max(d, d1[u] + d2[u]);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  printf("%d\n", d);
  return 0;
}

如果需要求出一條直徑上所有的節點，則可以在 DP 的過程中，記錄下每個節點能向下延伸的最長路徑與次長路徑（定義同上）所對應的子節點，在求 \(d\) 的同時記下對應的節點 \(u\)，使得 \(d = d_1[u] + d_2[u]\)，即可分別沿着從 \(u\) 開始的最長路徑的次長路徑對應的子節點一路向某個方向（對於無根樹，雖然這裏指定了 \(1\) 為樹的根，但仍需記錄每點跳轉的方向；對於有根樹，一路向上跳即可），遍歷直徑上所有的節點。

過程 2

這裏提供一種只使用一個數組進行的樹形 DP 方法。

我們定義 \(dp[u]\)：以 \(u\) 為根的子樹中，從 \(u\) 出發的最長路徑。那麼容易得出轉移方程：\(dp[u] = \max(dp[u], dp[v] + w(u, v))\)，其中的 &v& 為 \(u\) 的子節點，\(w(u, v)\) 表示所經過邊的權重。

對於樹的直徑，實際上是可以通過枚舉從某個節點出發不同的兩條路徑相加的最大值求出。因此，在 DP 求解的過程中，我們只需要在更新 \(dp[u]\) 之前，計算 \(d = \max(d, dp[u] + dp[v] + w(u, v))\) 即可算出直徑 \(d\)。

實現 2

代碼實現如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
const int N = 10000 + 10;

int n, d = 0;
int dp[N];
vector<int> E[N];

void dfs(int u, int fa) {
  for (int v : E[u]) {
    if (v == fa) continue;
    dfs(v, u);
    d = max(d, dp[u] + dp[v] + 1);
    dp[u] = max(dp[u], dp[v] + 1);
  }
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i < n; i++) {
    int u, v;
    scanf("%d %d", &u, &v);
    E[u].push_back(v), E[v].push_back(u);
  }
  dfs(1, 0);
  printf("%d\n", d);
  return 0;
}

性質

若樹上所有邊邊權均為正，則樹的所有直徑中點重合

證明：使用反證法。設兩條中點不重合的直徑分別為 \(\delta(s,t)\) 與 \(\delta(s',t')\)，中點分別為 \(x\) 與 \(x'\)。顯然，\(\delta(s,x) = \delta(x,t) = \delta(s',x') = \delta(x',t')\)。

無負權邊的樹所有直徑的中點重合

有 \(\delta(s,t') = \delta(s,x) + \delta(x,x') + \delta(x',t') > \delta(s,x) + \delta(x,t) = \delta(s,t)\)，與 \(\delta(s,t)\) 為樹上任意兩節點之間最長的簡單路徑矛盾，故性質得證。

習題

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用