【图论】树的直径

更新于 分类于 ， 阅读次数： 本文字数： 959 阅读时长 ≈ 1 分钟

树的直径求解

定义

树上任意两点最短路的最大值

方法一：两次DFS

条件：不能有负权边

第一次任一点出发找最短路的最大值点，必然是直径的一个端点

第二次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
27
28
29
30
31
32
33
int n;
vector<int> tree[N];
int d[N];
int cur; //记录第一次dfs的最远节点
void dfs(int rt, int fa)
{
    for (auto it : tree[rt])
    {
        if (it == fa)
            continue;
        d[it] = d[rt] + 1;
        if (d[it] > d[cur])
            cur = it;
        dfs(it, rt);
    }
}
int main()
{
    read(n);
    int u, v;
    for (int i = 1; i < n; i++)
    {
        read(u), read(v);
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    d[1] = 0;
    dfs(1, -1); //随便找一个节点开始
    d[cur] = 0;
    dfs(cur, -1);
    printf("%d\n", d[cur]);
    return 0;
}

方法二：树形dp

随便指定节点为根，dfs一个最远距离和次远距离，答案是所有节点最远+次远的最大值（代码道理更清楚）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int n;
vector<int> tree[N];
int d; // 树的直径
int d1[N], d2[N]; // 最远距离、次远距离的值
void dfs(int rt, int fa)
{
    d1[rt] = d2[rt] = 0;
    for (auto it : tree[rt])
    {
        if (it == fa)
            continue;
        dfs(it, rt); //每一支使得当前节点更新
        int tmp = d1[it] + 1;
        if (tmp > d1[rt]) //最大值更新
            d2[rt] = d1[rt], d1[rt] = tmp;
        else if (tmp > d2[rt]) //或者次大值更新
            d2[rt] = tmp;
    }
    d = max(d, d1[rt] + d2[rt]);
}