树的直径【程序员随笔文章】_编码库
首页 > 随笔文章 > 程序设计

树的直径【程序员随笔文章】

文章作者黑马程序员 发布时间2020-02-02 15:00:00 阅读次数 6 本文共计:3616 字 文章评论 0 汇编语言程序设计 程序设计实践 程序设计 程序员 windows程序设计 算法与程序设计 程序设计方法学 结构化程序设计 面向对象程序设计 程序设计语言
树的直径 [TOC] 定义:树的直径为树中最远的两个节点的距离之和。在求树的直径时一般有两种方法:树形dp或则两个BFS(DFS也可以)。 1.树形dp求解树的直径 思路:由树的直径定义可知:其树形d

程序员文章全文如下:

程序员成长之路

目录

  • 树的直径
    • 1.树形dp求解树的直径
    • 2.两次BFS求解树的直径
    • 3.两次DFS求解树的直径

定义:树的直径为树中最远的两个节点的距离之和。在求树的直径时一般有两种方法:树形dp或则两个BFS(DFS也可以)。

1.树形dp求解树的直径

思路:由树的直径定义可知:其树形dp的状态转移方程为:
\[ D[x]=max(D[y_i]+Edge(x_i,y_i)) \]
其中D[x]表示从节点x出发走向以x为根的子树,能够到达的最远距离。

#include<bits/stdc++.h>

using namespace std;
const int maxn=1e5+10;
struct node
{
    int nex,to,val;
}edge[maxn];
int head[maxn],dis[maxn],v[maxn],n,s,res=0,tot=0;
void add(int from,int to,int val)
{
    edge[++tot].to=to;
    edge[tot].val=val;
    edge[tot].nex=head[from];
    head[from]=tot;
}
void dp(int x)
{
    v[x]=1;
    for(int i=head[x];i!=-1;i=edge[i].nex)
    {
        int y=edge[i].to;
        if(v[y]) continue;
        dp(y);
        res=max(res,dis[x]+dis[y]+edge[i].val);
        dis[x]=max(dis[x],dis[y]+edge[i].val);
    }
}

int main()
{
    scanf("%d%d",&n,&s);
    memset(head,-1,sizeof(head));
    for(int i=1;i<n;++i)
    {
        int a,b,val;
        scanf("%d%d%d",&a,&b,&val);
        add(a,b,val);
        add(b,a,val);
    }
    dp(s);
    printf("%d\n",res);
    system("pause");
}

2.两次BFS求解树的直径

两次DFS或者BFS也可以求得树的直径,并且更容易的计算出直径上的具体结点。

3.两次DFS求解树的直径

如需求具体方案,只需在第二次dfs的时候记录一下即可,show code:

#include<bits/stdc++.h>

using namespace std;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f;
struct node
{
    int nex,to,val;
}edge[maxn];
int head[maxn],tot=0,n,m,dis[maxn],res;
bool v[maxn];
int start,ed;
inline void add(int from,int to,int val) 
{
    edge[++tot].to = to;
    edge[tot].val=val;
    edge[tot].nex=head[from];
    head[from]=tot;
}
void dfs(int x)
{
    v[x]=1;
    for(int i=head[x];i!=-1;i=edge[i].nex){
        int y=edge[i].to;
        if(v[y])    continue;
        dis[y]=dis[x]+edge[i].val;
        dfs(y);
    }
}

int main()
{
    memset(v,0,sizeof(v));
    memset(head,-1,sizeof(head));
    scanf("%d %d",&n,&m);
    for(int i=1;i<=m;++i){
        int a,b,val;
        scanf("%d %d %d",&a,&b,&val);
        add(a,b,val);
        add(b,a,val);
    }
    for(int i=1;i<=n;++i)
        dis[i]=(i==1)?0:inf;
    dfs(1);                     //找到树的一个端点
    res=0;
    for(int i=1;i<=n;++i) 
        if(dis[i]>res&&dis[i]!=inf){
            res=dis[i];        //找到1的一个最远的端点,start确定
            start=i;
        }
    memset(v, 0, sizeof(v));        //注意重新初始化
    for(int i=1;i<=n;++i)
        dis[i]=(i==start)?0:inf;
    dfs(start);
    res=0;                        //找到离端点最远的结点,距离即为直径
    for(int i=1;i<=n;++i) 
        if(dis[i]>res&&dis[i]!=inf){
            res=dis[i];
            ed=i;
        }
    printf("%d\n",res);
}

要通过每天不断学习,提高程序员的自我修养,加油,遇见未来

关键词: 程序设计报告,程序设计导引及在线实践,高质量程序设计指南
后台-系统设置-扩展变量-手机广告位-内容正文底部
关于源码库

本站文章仅代表作者观点,不代表本站立场,所有资源非营利性免费分享。
编码库致力于各类程序源代码、程序设计与应用、网络程序源代码的资源共享,希望广大程序员努力学习,让我们用科技改变世界。
树的直径【程序员随笔文章】:http://www.0314.online/webyunying/wjingyan/22922.html

后台-系统设置-扩展变量-手机广告位-评论底部广告位

合作伙伴

编码库

http://www.0314.online/

统计代码 | 冀ICP备19024639号-1

Powered By 编码库 信息来自互联网