树:树的直径

很久没写blog了,今天水一篇。
今天来讲讲树的直径

树的直径

什么?你不知道什么是树?点此处
什么是树的直径呢?
树的直径就是树中两个节点最远的距离。
那该如何求呢?
其实也很简单。

方法一:树形dp

我们可以运用树形dp,设

gxg_x

gx​ 表示从节点x出发走向以x为根的自述,能够到达最远节点的距离,若

edge(x,y)edge(x,y)

edge(x,y) 表示边权,y表示x的子节点,则有:

gx=max(gy+edge(x,y))g_x=max(g_y+edge(x,y))

gx​=max(gy​+edge(x,y))
接着,我们考虑经过节点x的最长链的长度,设为

FxF_x

Fx​,则答案为

maxx=1n(Fx)max_{x=1-n}(F_x)

maxx=1−n​(Fx​)
那么我们想如何转移

FxF_x

Fx​,显然

Fx=max(gyi+gyj+edge(x,yi)+edge(x,yj))F_x=max(g_{y_i}+g_{y_j}+edge(x,y_i)+edge(x,y_j))

Fx​=max(gyi​​+gyj​​+edge(x,yi​)+edge(x,yj​))
但是这样去枚举的时间复杂度难道不是很不能接受吗?
那我们想一想怎么优化吧~
请大家想一想g数组是怎么弄成的?
在未转移完g数组时,g数组是不是就指的是已做的儿子的max?是吧
那么我们就可以先转移F,再转移g了,具体实现看代码。

void dfs(int u,int fa){
for (int i=head[u];i;i=e[i].next){//链式前向星
int v=e[i].to;
if (v==fa) continue;
dfs(v,u);
ans=max(ans,g[u]+g[v]+e[i].w);//e[i].w指的是边权
g[u]=max(g[u],g[v]+e[i).w;
}
return;
}

方法二:两次BFS/DFS

我们设一棵树的根为root,那么先用DFS/BFS求出离root最远的点p,再从点p开始DFS/BFS,求出最远的q,那么p和q的路径就是树的直径。
因为不是的话,一定能找到更长的链,但与直径定义矛盾
具体证明留给读者。
就不来程序了。

总结

大家应该能看懂!点个赞吧!
对了,我的blog!
若有不当的地方,欢迎大家指出!

原创:https://www.panoramacn.com
源码网提供WordPress源码,帝国CMS源码discuz源码,微信小程序,小说源码,杰奇源码,thinkphp源码,ecshop模板源码,微擎模板源码,dede源码,织梦源码等。

专业搭建小说网站,小说程序,杰奇系列,微信小说系列,app系列小说

树:树的直径

免责声明,若由于商用引起版权纠纷,一切责任均由使用者承担。

您必须遵守我们的协议,如果您下载了该资源行为将被视为对《免责声明》全部内容的认可-> 联系客服 投诉资源
www.panoramacn.com资源全部来自互联网收集,仅供用于学习和交流,请勿用于商业用途。如有侵权、不妥之处,请联系站长并出示版权证明以便删除。 敬请谅解! 侵权删帖/违法举报/投稿等事物联系邮箱:2640602276@qq.com
未经允许不得转载:书荒源码源码网每日更新网站源码模板! » 树:树的直径
关注我们小说电影免费看
关注我们,获取更多的全网素材资源,有趣有料!
120000+人已关注
分享到:
赞(0) 打赏

评论抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

您的打赏就是我分享的动力!

支付宝扫一扫打赏

微信扫一扫打赏