zzoce 🧊
树的直径

树的直径

Fri Oct 04 2024
zzcoe
5 分钟
数据结构与算法 图论
849 字

树的直径，或称为树的宽度，是指树中任意两个节点之间最长路径的长度。在无向树中，这条路径也被称为最长简单路径。树的直径可以通过以下几个步骤计算得出：

  1. 选择任意一个节点 (X) 作为起点。
  2. 找到最远的节点 (Y)，即从 (X) 出发能够到达的最远的节点。
  3. 从节点 (Y) 出发，找到最远的节点 (Z)，即从 (Y) 出发能够到达的最远的节点。
  4. 路径 (Y) 到 (Z) 的长度即为树的直径。

这个方法基于的原理是：在一棵树中，从任意节点出发到达最远节点的路径上的某个节点，必定是从树的一端到另一端最长路径上的节点。因此，通过两次遍历（两次深度优先搜索或广度优先搜索），我们可以找到树的直径。

示例#

假设有一棵树，其边连接如下：1-2, 1-3, 2-4, 3-5, 3-6。树的直径是从节点 4 到节点 5 或 6 的路径，长度为 4。

应用#

树的直径概念不仅适用于树结构，也适用于无向图中寻找最长简单路径的问题。在实际应用中，树的直径可以用于网络设计、生物信息学（如在蛋白质结构分析中寻找最长链）等领域。

计算方法#

树的直径可以通过两次遍历树来计算：

  • 第一次遍历（可以是 DFS 或 BFS）从任意节点出发，找到距离它最远的节点 (Y)。
  • 第二次遍历从节点 (Y) 出发，找到距离 (Y) 最远的节点 (Z)，并记录这次遍历的最大距离。

这两次遍历确保了无论初始选择的节点在树的哪个位置，最终都能找到树的直径。

代码#

CPP
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
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e5 + 5; // 假设树的节点数不超过100000
vector<int> adj[MAXN]; // 邻接表存储树
int maxDist, farthestNode; // 存储最远距离和最远节点

// 深度优先搜索函数，node是当前节点，parent是父节点，dist是当前的距离
void dfs(int node, int parent, int dist) {
    if (dist > maxDist) { // 如果当前距离大于已知的最远距离
        maxDist = dist; // 更新最远距离
        farthestNode = node; // 更新最远节点
    }
    for (int nextNode : adj[node]) { // 遍历当前节点的所有邻接节点
        if (nextNode != parent) { // 如果邻接节点不是父节点
            dfs(nextNode, node, dist + 1); // 递归地进行深度优先搜索
        }
    }
}

// 计算树的直径
int treeDiameter(int n) {
    maxDist = -1; // 初始化最远距离
    dfs(1, 0, 0); // 从节点1开始进行第一次DFS
    maxDist = -1; // 重置最远距离
    dfs(farthestNode, 0, 0); // 从第一次DFS找到的最远节点开始进行第二次DFS
    return maxDist; // 返回树的直径
}

int main() {
    int n; // 树的节点数
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v; // 输入每条边连接的两个节点
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    cout << "The diameter of the tree is: " << treeDiameter(n) << endl;
    return 0;
}