求树径的线性算法 [英] Linear algorithm of finding tree diameter

问题描述

我有以下代码来查找树的直径：

I have the following code to find the diameter of a tree:

ALGORITHM: TREE_DIAMETER (T)

maxlength ← 0
for s ← 0 to s < |V[T]|
      do temp ← BSF(T, S)
            if maxlength < temp
                   maxlength ← temp
                   increment s by 1
return maxlength

但是该算法不能在线性时间内运行。尽可能保留上述代码的详细信息（例如：使用BSF），是否可以将其优化为线性时间？您可以使用伪代码。

But this algorithm does not run in linear time. Preserving the details of the above code as much as possible (Eg: using BSF), is it possible to optimize it to linear time? You can use pseudo-code.

推荐答案

这是一个简单的具有线性时间复杂度的算法：

1 ）选取任意顶点 v 。

2）使用BFS从 v 查找最远的顶点（我们称它为 u ）。

3）使用BFS从 u 查找最远的顶点再过一次（我们称它为 t ）。

然后 distance（u，t）是直径。

BFS仅被调用两次，因此时间复杂度是线性的。

Here is a simple algorithm with linear time complexity:
1)Pick an arbitrary vertex v.
2)Find the furthest vertex from v using BFS(let's call it u).
3)Find the furthest vertex from u using BFS one more time(let's call it t).
Then distance(u, t) is the diameter.
BFS is called only twice, so the time complexity is linear.

这篇关于求树径的线性算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！