算法 - 查找树中直径距离对的数量？

Question

我有一个非根的双向未加权非二叉树.我知道如何找到树的直径,树中任何一对点之间的最大距离,但我有兴趣找到具有该最大距离的对的数量.是否有算法可以找到直径距离优于O(V ^ 2)时间的对数,其中V是节点数？

谢谢!

Answer 1

是的，有一个时间为 O(V+E) 的算法。它只是求直径的修改版本。

正如我们所知，我们可以使用两次 BFS 调用来找到直径，方法是首先在任何节点上进行第一次调用，然后记住最后发现的节点 u 并运行第二次调用 BFS(u)，并记住最后发现的节点，比如 v。 u 和 v 之间的距离就是直径。

得出具有最大距离的对的数量。

1.在调用第一个BFS之前，初始化一个长度为|V|的数组距离 distance[s]=0.s 是任意节点上第一次 BFS 调用的起始顶点。

2.在BFS中，将while循环修改为：

while(Q is not empty)
 {
  e=deque(Q);
    for all vertices w adjacent to e
     {
       if(w is not visited)
        {
         enque(w)
         mark w as visited
         distance[w]=distance[e]+1
         parent[w]=e
        }
     }
 }

3.就像我说的，记住最后访问的节点，假设u是那个节点。现在计算与顶点 u 处于同一级别的顶点数。mark 是一个长度为 n 的数组，其所有值都初始化为 0，0 意味着该顶点最初未计算在内。

n1=0
for i = 1 to number of vertices
 {
  if(distance[i]==distance[u]&&mark[i]==0)
   {
    n1++
    mark[i]=1/*vertex counted*/
   }
 }  

n1 给出与顶点 u 处于同一级别的顶点数，现在对于所有具有 mark[i] = 1 的顶点，都将被标记，并且不会再次计数。

4.类似地，在对u执行第二次BFS之前，初始化另一个长度为|V|的数组distance2 且距离2[u]=0。

5.运行 BFS(u) 并再次获取最后发现的节点 v

6.重复第3步，这次在distance2数组上并采用不同的变量，例如n2=0，条件是

if(distance2[i]==distance2[v]&&mark[i]==0)
 n2++
else if(distance2[i]==distance2[v]&&mark[i]==1)
 set_common=1

7.set_common 是一个全局变量，当存在一组顶点时设置，使得任意两个顶点之间的路径是直径的路径，并且第一个 bfs 没有标记所有这些顶点，但确实标记了至少一个为什么标记[i]==1。

假设第一个 bfs 在第一次调用中确实标记了所有此类顶点，则 n2 将 = 0 并且 set_common 不会被设置，也没有必要。但这种情况与上面相同

在任何情况下，给出直径的对数为：=

(n+n2)组合2 - X=(n1+n2)!/((2!)((n1+n2-2)!)) - X

我将详细说明 X 是什么。否则对的数量 = n1*n2，这是当 2 个不相交的顶点集给出直径时的情况

所以使用的条件是

  if(n2==0||set_common==1)
    number_of_pairs=(n1+n2)C2-X
  else n1*n2

现在谈论 X。标记的顶点可能有共同的父级。在这种情况下，我们不能计算这些组合。因此，在使用上述条件之前，建议运行以下算法

  X=0/*Initialize*/
 for(i = 1 to number of vertices)
  {
   s = 0,p = -1
   if(mark[i]==0)
    continue
   else
   {
    s++
    if(p==-1)
     p=parent[i]
    while((i+1)<=number_of_vertices&& p==parent[i+1])
     {s++;i++}
   }
   if(s>1)
    X=X+sC2
 }

正确性证明

很简单，因为BFS是一层层遍历一棵树，n1 将为您提供 u 级别的顶点数量，n2 为您提供 v 级别的顶点数量，并且因为 u 和 v 之间的距离 = 直径因此，u 级别上的任意顶点与 v 级别上的任意顶点之间的距离将等于直径。

所花费的时间为 2(|V|) + 2*time_of_DFS=O(V+E)。