MemoryGarden's Blog

努力 -----------大能猫

C++博客 首页 新随笔 联系 聚合 管理
  118 Posts :: 11 Stories :: 20 Comments :: 0 Trackbacks
from -> Roba

怒赞roba


树的直径(Diameter)是指树上的最长简单路。
直径的求法:两遍BFS (or DFS)
任选一点u为起点,对树进行BFS遍历,找出离u最远的点v
以v为起点,再进行BFS遍历,找出离v最远的点w。则v到w的路径长度即为树的直径
*简单证明
于是原问题可以在O(E)时间内求出

关键在于证明第一次遍历的正确性,也就是对于任意点u,距离它最远的点v一定是最长路的一端。
如果u在最长路上,那么v一定是最长路的一端。可以用反证法:假设v不是最长路的一端,则存在另一点v’使得(u→v’)是最长路的一部分,于是len(u→v’) > len(u→v)。但这与条件“v是距u最远的点”矛盾。
如果u不在最长路上,则u到其距最远点v的路与最长路一定有一交点c,且(c→v)与最长路的后半段重合(why?),即v一定是最长路的一端
posted on 2009-10-08 00:46 memorygarden 阅读(3446) 评论(1)  编辑 收藏 引用 所属分类: 图论

Feedback

# re: 树的直径[未登录] 2013-02-28 02:09
回答why:
因为是树是连通的,所以u必有一条路径c和最长路径L相交,len(c)>=1,L被分为两部分,一部分l1,一部分l2
假设第一次dfs过后,所求最长路径lu端不在L上,那么len(lu)>=len(c)+len(l1)(l1,l2对称,取l1或者l2都一样)
len(l2+c+lu)>len(l1+l2),矛盾.


虽然是挖坟,不过分享知识更重要,呵呵  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理