6

我们得到一个表格的邻接列表

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是唯一的选择吗？

4

2 回答 2

1

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

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

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

于 2013-03-02T21:10:16.817 回答
-2

如果我正确理解了您的问题，那么您正在尝试在生成树中找到最长的成本路径。

您可以在 2 次完整遍历中找到路径，即 O(2N) ~ O(N) 对于较大的 N 值。

你应该做下面的步骤。

  1. 选择生成树中的任何节点。
  2. 从节点运行任何算法（DFS 或 BFS），并从该节点找到最长的成本路径。

这不会是您从随机选择一个节点开始的最长成本路径。

  1. 从步骤 2 中找到的最长成本路径的最后一个节点再运行一次 BFS 或 DFS。
  2. 这次你得到的最长成本路径将是生成树中最长的成本路径。

您不必从每个节点运行 DFS。

于 2016-04-21T05:02:00.303 回答