计算树中边两侧的节点数

Question

这里的树是指具有n个节点和n-1条边的无环无向图。对于树中的每条边，计算它两边的节点数。如果在删除边缘时，你得到两棵树有 a 和 b 个节点，那么我想找到这些值 a 和 b 用于树中的所有边（理想情况下在 O(n) 时间内）。

直觉上，我觉得从所有 "leaf" 个节点开始的多源 BFS 会产生一个答案，但我无法将其转化为代码。

为了加分，请提供适用于任何一般图形的算法。

Answer 1

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

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

之后，我们就知道了每条边一侧的节点数。另一边的数字就是总数减去我们找到的数字。

（你的问题的额外学分版本涉及在此之上的图中找到桥梁作为一个重要的部分，因此如果你真的感兴趣的话，应该作为一个单独的问题来问.)

Answer 2

注意n=b-a+1。因此，您无需计算边缘的两侧。这大大简化了事情。从根开始对节点进行正常递归就足够了。由于你的树是无向的，所以你实际上没有 "root"，只需摘下其中一片叶子即可。

你要做的是 "go down" 树，直到到达底部。然后你从那里倒数。叶子 returns 1，每个递归步骤对每条边的 return 值求和，然后递增 1。

Answer 3

考虑以下树：

如果我们剪掉节点1和节点2之间的边，树肯定会分裂成两棵树，因为根据树属性:

，两个节点之间只有一条唯一的边

和

  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]

时间和 space 复杂度都 O(n)。

Answer 4

这是 Java 代码。函数 countEdges() 以树的邻接表作为参数，还有当前节点和当前节点的父节点（这里的父节点是指当前节点是由该 DFS 中的父节点引入的）。

这里edge[][]存储的是edge[i][j]一侧的节点数，显然另一侧的节点数会等于（总节点数-edge[i] [j]).

int edge[][];  
int countEdges(ArrayList<Integer> adj[], int cur, int par) {
    // If current nodes is leaf node and is not the node provided by the calling function then return 1 
    if(adj[cur].size() == 1 && par != 0) return 1;
    int count = 1;
    // count the number of nodes recursively for each neighbor of current node.
    for(int neighbor: adj[cur]) {
        if(neighbor == par) continue;
        count += countEdges(adj, neighbor, cur);    
    }
    // while returning from recursion assign the result obtained in the edge[][] matrix.
    return edge[par][cur] = count;
}

由于我们在 DFS 中只访问每个节点一次，时间复杂度应该是 O(V)。

计算树中边两侧的节点数

Calculate the number of nodes on either side of an edge in a tree

algorithm

tree

graph-theory