问小白 wenxiaobai
资讯
历史
科技
环境与自然
成长
游戏
财经
文学与艺术
美食
健康
家居
文化
情感
汽车
三农
军事
旅行
运动
教育
生活
星座命理

树的直径解释

创作时间:
作者:
@小白创作中心

树的直径解释

引用
CSDN
1.
https://blog.csdn.net/ATION001/article/details/145968592

定义

树上任意两点之间的最长简单路径即为「树的直径」。

性质

  1. 树的直径不一定唯一。
    举个例子,比如说有这么一棵树:

    假设这张图中每一条边边权均为1 11,那么手动推算一下,发现直径有:
    2 -> 1 -> 4 -> 5

    3 -> 1 -> 4 -> 6
    (自己手动去推,这里就不一一例举了)……

  2. 树的直径的端点一定是深度为1 11的点。
    对于这种图论的知识点还是先画张图(边权都是1 11):
    现在我们找的点对是( 2 , 4 ) (2,4)(2,4),假设( 2 , 4 ) (2,4)(2,4)是这棵树的直径。
    但是,2 22/4 44除了两个点向连接的那条边之外,2 22还连接了1 11/3 33,4 44连接了5 55/6 66。显然还能继续拓展,可以证明,( 2 , 4 ) (2,4)(2,4)一定不是树的直径。

  3. 树的直径若有多条,那么所有的树的直径一定交汇于1 11个或2 22个点。这1 11个或2 22个点即为「树的中心」。
    我们采用反证法进行证明:
    假设两条直径( A , B ) (A,B)(A,B),( C , D ) (C,D)(C,D)互不相交,因为树是联通的,所以一定存在一条路径连接这两条直径上的点。我们设( A , B ) (A,B)(A,B)上某一个点为x xx,( C , D ) (C,D)(C,D)上某一个点为y yy。
    现在,我们从A AA出发,依次经过x xx、y yy到达D DD。显然,新路径比( A , B ) (A,B)(A,B)要长,与( A , B ) (A,B)(A,B)为直径互相矛盾,所以假设不成立。
    不过,需要注意上面假设成立的条件是:不存在3 33个以上的连续的边权为0 00的路径。
    比如说下面这张图:

    假设我们选择路径( 1 , 2 ) (1,2)(1,2)与( 5 , 4 ) (5,4)(5,4),这两条路径没有相交且均为「树的直径」,这种情况下,假设失效。

  4. 树上任意点i ii,距离其最远的点x xx,一定是树的直径的某个端点
    同样采用反证法,假设x xx不是直径的某个端点,那么存在一条从i ii开始的路径,比从i ii到x xx要更长。
    矛盾点就在于,如果x xx不为直径的某个端点,那么i ii到x xx的路径不可能是最长的路径。但是根据x xx的定义,x xx是距离i ii最远的点。意味着i ii到x xx的路径是树的最长路径之一,显然假设不成立。
    所以,x xx一定是树的直径的某个端点。

解法

解法1:Floyd

先运行一遍 Floyd,然后找出最长路径的长度。
时间复杂度O ( n 3 ) O(n^3)O(n3),效率低下。

解法2:两遍 DFS

第一遍,我们从任意一点开始跑 DFS。为了方便,我们通常选择从1 11节点开始跑。
求出距离其最远的点x xx。
然后,从x xx开始跑第二遍 DFS。找出距离其最远的点y yy,顺带求出直径的长度。
时间复杂度O ( n ) O(n)O(n),比较优秀。

解法3:树形 DP

在上面 DFS 的解法中,你可能会发现一个问题:解法2 22跑不了负边权
Hack
Input:

  
9
1 2 -3
1 3 1
2 4 -7
4 5 4
4 6 -2
6 7 -3
7 8 -9
7 9 3
  

Output:

  
5
  

我们需要找出一条最长链和一条次长链,且最长链和次长链互不相交。
求出从任意节点出发,最长链的长度和次长链的长度。
用树形 DP 来维护就行了。

例题:B4016 树的直径

两遍 DFS 解法

  
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,sum,id;
vector<int>v[100005];
void dfs(int x,int fa,int len){
    if(len>=sum){
        sum=len,id=x;
    }
    for(auto z:v[x]){
        if(z!=fa){
            dfs(z,x,len+1);
        }
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,-1,0);
    dfs(id,-1,0);
    cout<<sum;
    return 0;
}
  

树形 DP 解法

  
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,dp[200005],ans=-1e18,dp1[200005];
vector<int>v[200005];
void dfs(int x,int fa){
    for(auto z:v[x]){
        if(z!=fa){
            dfs(z,x);
            if(dp[x]<=dp[z]+1){
                dp1[x]=dp[x];
                dp[x]=dp[z]+1;
            }else if(dp1[x]<=dp[z]+1){
                dp1[x]=dp[z]+1;
            }
        }
    }
    ans=max(ans,dp[x]+dp1[x]);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,x,y;i<n;i++){
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1,-1);
    cout<<ans;
    return 0;
}
  
© 2023 北京元石科技有限公司 ◎ 京公网安备 11010802042949号