计算树中边缘两侧的节点数量

Question

此处的树意味着一个非循环无向图，其中n节点和n-1边缘。对于树中的每个边，计算其两侧的节点数。如果去掉边缘，你有一个和b数量的节点两棵树，那么我想找到这些值一个和b树中的所有边缘（最好是在O（n）的时间）。

直觉上我觉得从所有“叶”节点开始的多源BFS会产生答案，但我无法将其转换为代码。

要获得额外功劳，请提供适用于任何常规图形的算法。

Answer 1

从任何节点运行深度优先搜索（如果您更喜欢广度优先搜索）。 该节点将被称为根节点，并且所有边将仅在从根节点开始的方向上遍历。

对于每个节点，我们计算其有根子树中的节点数。 第一次访问节点时，我们将此数字设置为1. 当子树的子树完全访问时，我们将其子树的大小添加到父树。

在此之后，我们知道每个边的一侧的节点数量。 另一方面的数字只是总数减去我们找到的数字。

（你的问题的额外信用的版本包括在此之上寻找图中的桥梁作为一个不平凡的一部分，因此值得被问作为一个单独的问题，如果你真的有兴趣。）

Answer 2

请注意，n=b-a+1。由于这个原因，你不需要计算边的两边。这大大简化了事情。从根开始的节点上的正常递归就足够了。既然你的树是无向的，你并没有真正的“根”，只需选择其中一片树叶即可。

你想要做的是“向下”树，直到到达底部。然后你从那里倒数。叶返回1，并且每个递归步骤总和为每个边缘的返回值，然后通过递增1

Answer 3

考虑以下树：

1 
/\ 
    2 3 
/\ | \ 
5 6 7 8 

如果我们切节点1和2之间的边缘，该树一定会分裂成两个树，因为是根据树财产两个节点之间只有一个独特优势：

1 
\ 
    3 
    | \ 
    7 8 

和

2 
/\ 
5 6 

因此，现在的a是植根于1的节点数量，而b是植根于2的节点数量。

> Run one DFS considering any node as root. 

> During DFS, for each node x, calculate nodes[x] and parent[x] where 
     nodes [x] = k means number of nodes of sub-tree rooted at x is k 
     parent[x] = y means y is parent of x. 

> For any edge between node x and y where parent[x] = y: 
      a := nodes[root] - nodes[x] 
      b := nodes[x] 

时间和空间复杂度均为O(n)。