algorithm - 如何找到树的任意两个顶点之间的边或顶点的数量？

Question

它是一棵通用树(无环图)，所以这样的路径只能有一条。我可以为此使用什么算法？

编辑:

需要找到树中所有顶点对的路径

Answer 1

我想在这里扩展@templatetypedef 的答案¹。

请注意，在您的问题中，您需要为树中的每对节点至少执行一次写入。其中有 n*(n-1)/2。
因此，就大O符号而言，你找不到比O(n^2)运行得更好的算法。

现在，使用 DFS或 BFS找到每个节点的路径。它将在 O(n+m) 中运行(n 个顶点，m 个边)。但由于它是一棵树，我们知道 m=n-1，从而为 BFS/DFS 提供 O(n)。请注意，在来自某个节点 v 的单个 BFS/DFS 中 - 您会为每个节点 u 获得 d(v,u)。

如果您对每个节点重复它，它将得到 O(n^2) - 这在大 O 表示法方面是最佳的。我同意您可能会通过一些优化获得更好的常量，但仅此而已。

---

(1) 以评论的形式开始，但它太长了，我认为它值得回答。