algorithm - 确定树中两个随机节点之间的距离

Question

给定一棵通用树，我想要两个节点之间的距离v和w。

维基百科声明如下：

计算最低共同祖先可能很有用，例如，作为确定树中节点对之间距离的过程的一部分：从 v 到 w 的距离可以计算为从根到 v 的距离，加上距离从根到 w，减去从根到它们最低共同祖先的距离的两倍。

假设d(x)表示节点x到我们设置的根的距离1。表示两个顶点和d(x,y)之间的距离。表示顶点对和的最低共同祖先。xylca(x,y)xy

因此，如果我们有4并且8，lca(4,8) = 2因此，根据上面的描述，d(4,8) = d(4) + d(8) - 2 * d(lca(4,8)) = 2 + 3 - 2 * 1 = 3。太好了，这有效！

(8,3)但是，对于顶点对( lca(8,3) = 2) ，上述情况似乎失败了。然而，从图中可以看出d(8,3) = d(8) + d(3) - 2 * d(2) = 3 + 1 - 2 * 1 = 2.距离是不正确的。d(8,3) = 4对于跨越定义根的任何内容，该算法似乎都失败了。

我错过了什么？

Answer 1

你错过了lca(8,3) = 1，而不是= 2。因此，d(1) == 0这使得它：

d(8,3) = d(8) + d(3) - 2 * d(1) = 3 + 1 - 2 * 0 = 4

Answer 2

对于适当的2节点，即右边的节点，d(lca(8,2))== 0，而不是推导中的 1。从根（在这种情况下为 lca）到自身的距离为零。所以

d(8,2) = d(8) + d(2) - 2 * d(lca(8,2)) = 3 + 1 - 2 * 0 = 4

您标记了两个节点的事实2可能令人困惑。

编辑：帖子已经过编辑，原来标记为 2 的节点现在标记为 3。在这种情况下，推导现在是正确的，但语句

 the distance d(8,2) = 4 as can be seen on the graph

不正确，d(8,2) = 2。