Diameter of a tree

简介

　　在之前的文章里我讨论过计算图里最短路径的几种方法，一个是Dijkstra's algorithm，一个是Bellman-Ford Algorithm。它们都是针对一个比较通用形式的图来进行计算处理的。在实际的应用中，有些比较特殊的图，在计算它们的最短路径的应用中往往还有一些更加简单的方法。

 

问题描述 

　　Given a graph that is a tree (connected and acyclic), find the longest path, i.e., a pair of vertices v and w that are as far apart as possible. Your algorithm should run in linear time.

 

问题分析

　　这个问题的描述里既说到了图也提到了树。从概念上来说，树是图的一个特殊的形式，对于一个连通的无环图来说，它就是一棵树。而要计算一棵树或者图的直径，我们需要计算图里面最长的路径。在不考虑树这种特殊的结构的情况下，我们可以直接运用Dijkstra's algorithm或者Bellman-Ford algorithm。不过这两种算法的时间复杂度都不是单纯的线性时间。

　　所以到这里我们就知道，不能直接用前面的算法来生搬硬套。看来能优化的地方就在于树这个前提了。以下图的树为例：

　　我们要求一个节点到其他节点的距离或者最长最短距离，它们都有一个比较有意思的特性。从一个节点到另外一个节点只有一条且唯一的一条路径。这里基于一个不重复访问原有节点的情况下。 所以我们要计算一个节点到其他所有节点的距离，只需要采用一种方式遍历树就可以了。

　　这个树的关键特性在于从给定的一个任意起点来说，它到其他节点都不可能构成环。所以它就不可能在通过其他的路径再访问到它访问过的节点。这样就不存在有我后面会访问到之前遍历过的节点。

　　 现在假设给定了一个点，我们计算出来了它到所有其他节点的距离。然后呢？这一步对于问题的解决有什么作用呢？假设在上图的示例中，我们选定了最初始的节点７：

　　从它作为起始点开始，假定我们选择BFS作为遍历计算的方法。我们最终找到距离它最远的节点９：

　　这一步找到了距离７最远的节点９。这一步有什么作用呢？在最简化的情况，假设这个最远的节点和源节点分别在根节点的两个子树中。那么这个目标节点相对于根节点来说一定是在这个子树中距离最长的点。如果要求树的直径的话，这边就相当于找到了一个点。

　　对于另外一种情况呢？假设这个最远的节点和源节点都在根节点的一个子树中。那么它们构成的这个最长路径肯定是从源节点到一个它们的最近公共父节点，然后再往叶节点方向到另外一个节点。在这种情况下，这个最长距离节点和源节点到它们公共父节点的距离之和肯定是当前最大的。假定以这个最近公共父节点作为一个树的根，那么这个问题就可以概括成上一个情况。

　　对于树来说，从一个非根节点到另外一个节点的最长距离很可能是通过根节点并到达另外一个子树的叶节点的长度。其实这一步相当于间接的求出来了从根节点到其他节点的最大距离。而下一步则需要根据当前这个节点９计算它到所有其他节点的距离。如果找到了所有距离值最大的那个，就找到了图的直径。

 

实现考虑

　　基于前面的讨论，概括起来就是两个广度优先遍历的方式可以找到这个树的直径。在一般的BFS实现里，我们只是用一个boolean数组来表示访问过元素的标记。这里需要一个额外的数组int[] dist，用来记录从源节点到目标节点的距离。每次遍历的时候碰到新的节点就计算它到源节点的距离。然后在遍历完之后查找距离最远的节点，作为直径的一个节点。

　　剩下的事情就是根据这个节点再次重复上面的过程找距离最长的点，这样就找到了直径节点和值了。

　　其实这部分的代码比较简单，这里就不详细列出来了。

 

总结

　　树是一种特殊的图，所以求树的直径可以用一种更加高效的办法，而不需要直接搬用传统的Dijkstra's 算法或者Bellman-Ford算法。这里为什么随意给定一个节点找到它距离最远的点就是直径的一个点的问题还有一些小的地方没有深入分析。需要进一步思考。

 

参考材料

algorithms