我有一棵无根的双向非加权非二叉树。我知道如何找到树的直径，即树中任意一对点之间的最大距离，但是我对找到具有该最大距离的对数感兴趣。是否有一种算法可以找到直径距离比O(V ^ 2)时间更好的对数，其中V是节点数？
谢谢!
最佳答案
是的，有一个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处于同一级别的顶点数量。 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。并且distance2 [u] = 0。
5，运行BFS(u)并再次获取发现的最后一个节点，然后说v
6.重复第三步，这次是在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不会标记所有这些顶点，但会标记至少一个顶点为什么mark [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)。
关于算法-查找树中具有直径距离的对的数量？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/29704376/