我们得到一个形式的邻接表
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 是唯一的选择吗？
最佳答案
我理解你的问题是要求从集合 F 中找到一对节点，以便这两个节点之间的唯一路径尽可能长。该路径是唯一的，因为您的图是一棵树。
这个问题可以通过从 F 中的每个节点执行 DFS 来简单地解决，如您提到的，对于 O(n k) 解决方案，其中 n 是图的大小，k 是集合 F 的大小。
但是，您可以通过分而治之的方法更快地解决它。从图中选择任何节点 R，并使用单个 DFS 将距离 Dist(R, a) 制成表格，以每个其他节点 a a 为单位，同时将节点划分为子树 S1,...,Sm，其中 m 是来自 R 的边；也就是说，这些是卡在根 R 上的 m 棵树。现在，对于属于不同子树的任何 f 和 g，它认为它们之间的路径有 Dist(R, f) + Dist(R, g) 条边，所以可以在 O(k^2) 时间内搜索最长的此类路径。此外，您还必须递归到子问题 S1,...,Sm 以涵盖最长路径在其中一棵树内的情况。整体复杂度可能低于 O(n k)，但数学作为练习留给读者。
关于algorithm - 如何在图中找到最长的路径？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15178178/