《Introduction to Algorithm》22.2-8
今天复习看到一题,试着证明了一下,题目简洁很有意思.
The diameter of a tree T = (V,E) is defined as , that is, the largest of all shortest-path distances in the tree. Give an efficient algorithm to compute the diameter of a tree, and analyze the running time of your algorithm.
总之,就是求树T的最远的两个节点的距离
算法:
1.对任意点跑DFS,得到最远的点s。
2.对点s跑DFS,得到最远的点t
就是最远距离
分析:(算法、实现都是浮云,分析才是王道) 时间复杂度O(V+E)