我有一棵非根的双向无权非二叉树。我知道如何找到树的直径，即树中任意两点之间的最大距离，但我想找出具有该最大距离的配对数量。是否有一种算法可以在O（V ^ 2）时间内更好地找到直径距离的配对数量，其中V是节点数？谢谢！
2个回答
2
是的，有一种底部向上的线性时间算法类似于仅查找直径的算法。以下是Java风格的伪代码签名; 我将把算法本身留作练习。
class Node {
Collection<Node> children;
}
class Result {
int height; // height of the tree
int num_deep_nodes; // number of nodes whose depth equals the height
int diameter; // length of the longest path inside the tree
int num_long_paths; // number of pairs of nodes at distance |diameter|
}
Result computeNumberOfLongPaths(Node root); // recursive
- David Eisenstat
1
对不起，我仍然没有看到算法。你能详细说明一下computeNumberOfLongPaths()吗？ - identicon
1
有一个时间复杂度为O(V+E)的算法，它是通过修改查找直径的方法得到的。
我们知道，可以使用两次BFS调用来找到直径。首先在任何节点上进行第一次调用，记住最后发现的节点u，然后运行第二个调用BFS(u)，并记住最后发现的节点v。u和v之间的距离给出了直径。
现在考虑具有最大距离的配对数。
1.在调用第一个BFS之前，初始化长度为|V|的数组distance，并将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数组，其中distance2[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没有标记所有这些顶点但至少标记了其中一个顶点时，它被设置。
假设第一个bfs在第一次调用中标记了所有这样的顶点，则n2将等于0，set_common也不会被设置，也没有必要。但这种情况与上述情况相同。
无论哪种情况，给出直径的点对数为：
(n+n2)组合2 - X=(n1+n2)!/((2!)((n1+n2-2)!)) - X
我将详细解释X是什么。否则，点对的数量为n1*n2，这是两个不相交的顶点集给出直径的情况。
因此使用的条件是
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 * DFS时间= O（V + E）。
- Sumeet
7
我已经进行了必要的编辑和处理了您提到的情况。如果我有错误，请指出来。 - Sumeet
我认为你不能从任意节点开始执行BFS。我认为你必须从任意节点执行一次BFS到一个节点s，然后再从s到u执行另一次BFS。 - identicon
根据算法，答案应该是9 C 2 = 36，但实际答案是36 + 33 = 27。 - identicon
这是因为被计算的额外对数。因为具有共同父节点的标记顶点不是有用的对，所以我已经将它们减去了。现在这个算法应该可以正常工作了。 - Sumeet
显示剩余2条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接