对于树的最远两节点的距离的了解
对于树的最远两节点的距离的理解
定义:n个节点的树,任选一个节点V0,找到距离它最远的节点V1,再找距离V1最远的节点V2,edge(V1,V2) 即为树的的最长枝.
理解:
Condition 1: edge(V0,V1)若经过root,则edge(root,V1)即为距离root最长,或次长的边.
因此,再从V1出发,找距离V1最远的节点V2,edge(V1,V2)必定通过root,所以可以看成是找距离root最远的节点V2(不能回头搜索V1),
所以树的直径为:edge(V1,root)+edge(root,V2) 且V1,V2必定为叶子,如果不是叶子,那它必定还能向下搜索,从而存在更长的边.
Condition 2: edge(V0,V1)若不经过root,则它是root的以V0为根节点的子树,所以可以看成找距离V0最远的节点V2(不回头搜索V1),
所以树的直径为:edge(V1,V0)+edge(V0,V2) 且V1,V2必定为叶子.
若理解有误,请告诉我.
典型题目:大臣的旅费