它是一棵通用树(无环图)，所以这样的路径只能有一条。我可以为此使用什么算法？
编辑:
需要找到树中所有顶点对的路径
最佳答案
我想在这里扩展@templatetypedef 的答案1。
请注意，在您的问题中，您需要为树中的每对节点至少执行一次写入。其中有 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) 以评论的形式开始，但它太长了，我认为它值得回答。
关于algorithm - 如何找到树的任意两个顶点之间的边或顶点的数量？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21662649/