python - 给定一棵树 T = (V, E)，找到从顶点 v 到顶点 w 的直接路径

Question

我被困在我的算法分配中，它要求在时间复杂度 O（dist（v，w））中找到从顶点 v 到顶点 w 的 n 个顶点（非循环间接图）的树（V，E）中的直接路径。我必须找到一个预处理（在 O(n) 中运行）来存储一些信息，这样我才能达到 O(dist(v, w)) 的时间复杂度。

我需要了解预处理中存储的内容，这将有助于稍后的算法。

没有完整的解决方案。

我已经尝试存储可能的路径，但是要创建一个全局 Adj 列表，我需要二次时间 O(n^2)。Dijkstra 也运行在所要求的时间复杂度之上（以及网络的所有路由算法）。树中的两个节点具有唯一的路径。

还尝试使用动态编程来存储已经发现的所有路径，但我想我已经克服了线性时间。运行 BFS 并存储所有以前的路径，例如：(node, node) : next hop

(A, B) : B and (B, A) : A
(B, C) : C (C, B): B (A, C) : B and (C, A): B

因此我需要(1 + 2 + 3 + 4 + 5 + ... + n - 1 + n) = n^2

Answer 1

如果您的网络是一棵树，那么每个顶点只有一个“入站”边。因此，您应该尝试遍历从 W 到 V 的链接（沿着入站边缘），而不是相反。这将为您提供相反顺序的路径。将其存储在列表中并将其反转以产生结果。

请注意，如果您还没有办法从下到上遍历树，您可能需要构建一个顶点字典 {child:parent} 来执行此操作。构建这个字典需要 O(E) 时间，然后找到路径需要 dist(V,W) 时间。