[关闭]
@Junlier 2018-09-22T14:21:16.000000Z 字数 746 阅读 3775

求树的直径算法

图论——树的直径
嗯,上次考试才发现自己连树的直径都只会......(弱到家了......)

树的直径

树的直径是树上的最长路

求法:2遍

没错,真的这么简单......

  1. 先随便找个点i开始,然后找到一条最长路径(假设终点是)
  2. 然后从u开始再一次,再找到一条最长路径(假设终点是),就是树的直径了......
    PS:树的直径可以有多条(想想定义就知道)

证明:为什么呢?

假设树的直径是,第一次找到
如果我们找到了树的直径的一端,那么第二次就一定可以找到树的直径对吧
那么证明转化成了第一次是否找到了树的直径的一端
PS:建议自己手动画棵树来一边看着证明 效果更佳

首先假设i在最长路径上:

  • 反证法:
  • 如果找到的(i,j)不是(i,u),那么(i,j)一定可以和(i,v)拼成另一条更长路(j,v)
    (因为(i,j)>=(i,u)而等于正印证了上面讲到的多条直径),所以与假设(u,v)是最长路不符,那么猜想的方法成立

如果i不在最长路上呢?

  1. 首先肯定可以和最长路上的一个点(从到最长路最先遇到的点)连通对吧
  2. 我们假设是最长路距离较远的一个末端,那么从找出去的最长路一定会到
    • 证明:如果(i,j)不是(i,u)(即(i,j)>(i,u)),那么(i,j)+(i,k)>(j,u),即我们找到了另一条(j,k)>(j,u),那么说明我们假设的直径(u,v)又可以被更长的(k,v)更新,假设不成立,那么猜想成立,证明完毕

总结一下

综上所述,两遍可以找到树的直径
而树的直径在很多图论题里面是很有用的,这种方法就保证了我们的时间复杂度O(n)
为我们其他计算提供了更优的复杂度空间。。。

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注