如何在图中找到最长路径？

Question

我们获得了表格的邻接列表

U -> (U,V,C) -> (U,V,C) ...  
U2 -> ...  
U3 -> ...  
.  
.  
etc

(U,V,C) 意味着从U到V的边缘成本为C.

给定的邻接列表用于具有N个节点的单个连接树,因此包含N-1个边缘.

给出了一组节点F=F1,F2,F3...Fk.

现在问题是找到F中节点之间最长路径的最佳方法是什么？是否可以在O(N)中进行？

F中每个节点的DFS是唯一的选择吗？

Answer 1

我理解你的问题是要求从集合 F 中找到一对节点，以便这两个节点之间的唯一路径尽可能长。该路径是唯一的，因为您的图是一棵树。

正如您提到的，对于 O(nk) 解决方案，其中 n 是图的大小，k 是集合 F 的大小，通过从 F 中的每个节点执行 DFS 可以轻松解决该问题。

但是，您可以通过分而治之的方法更快地解决它。从图中选取任意节点 R，并使用单个 DFS 来列出到每个其他节点 aa 的距离 Dist(R, a)，同时将节点划分为子树 S1,...,Sm，其中 m 是子树的数量R 的边；也就是说，这些是挂在根 R 处的 m 棵树。现在，对于属于不同子树的任何 f 和 g，它们之间的路径具有 Dist(R, f) + Dist(R, g) 边，因此可以在 O(k^2) 时间内搜索最长的此类路径。此外，您还必须递归到子问题 S1,...,Sm 以涵盖最长路径位于其中一棵树内的情况。整体复杂度可能低于 O(nk)，但数学运算留给读者作为练习。