树中最长路径的线性时间算法 [英] Linear time algorithm for longest path in tree

问题描述

有人给我一个关于让我感到困惑的任务的问题.我可能只是在想这个问题而已...问题出在后面.

I have been given a question on an assignment that has got me stumped. I may just be thinking too hard about it... The question follows.

使用线性时间算法来确定非循环无向图(即树)中最长的未加权路径.

我的初衷是使用DFS.但是似乎DFS只会给我从我开始的节点到另一个顶点的最长路径.但是，问题需要的是树中最长的路径……而不是从我开始的节点开始的最长路径.有人可以让我挺直吗?

My first intention is to go with a DFS. But it seems like a DFS would only give me the longest path from the node I start at to another vertex; however, the problem asks for the longest path in the tree... not the longest path from the node I start at. Could someone set me straight?

谢谢.

推荐答案

一种这样的方法是选取任意一个节点A，并在线性时间内计算到所有其他节点的距离.假设B最远离A.在步骤2中，找到最远离B的节点.

One such method is to pick any node, A, and in linear time compute distances to all other nodes. Suppose B is most distant from A. In step 2, find the node most distant from B.

让d(P，Q)表示从P到Q的距离.请注意，如果E是A，B，C的最低共同祖先，则d(A，B)= d(A，E)+ d(E，B)，还请注意d(E，B)≥d(E，C).

Let d(P,Q) denote distance from P to Q. Note that if E is the lowest common ancestor of A, B, C, then d(A,B) = d(A,E)+d(E,B) and also note that d(E,B) ≥ d(E,C).

算法或方法–找到与任何A距离最远的B；发现C最远离B；声称d(B，C)在图中所有顶点对上都最大–似乎是合理的，但上述方法不能证明这一点.

Edit 1: The algorithm or method – find B most distant from any A; find C most distant from B; claim that d(B,C) is maximal over all vertex pairs in the graph – seems to be sound, but the above does not prove it.

一方面，不必是d(E，B)≥d(E，C)，另一方面，仅凭此不足以建立d(B，C)≥d(F，G)，其中F，G是树中的任何节点....

On one hand, it need not be that d(E,B) ≥ d(E,C), and on another, that alone would not be quite enough to establish d(B,C) ≥ d(F,G) where F, G are any nodes in the tree. ...

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