The center of the node in the tree (in the minimum sum of distances)

Question

My problem is this:

For the tree (V, E), find the center of node v such that the sum {w in V} [dist (v, w)] is minimal, where dist (v, w) is the number of edges in the shortest path from v to w. The algorithm should be executed in O (n) time (n is the number of nodes in the tree).

Questions here and here also request the center of the node, but define it differently.

I didn’t go through these steps very carefully, but I really think that the solution to my problem should be similar to the solution to this problem .

However, I decided that I should share my problem with the community, since it took me a while to go to the link , which, however, does not directly answer the question.

Answer 1

I came up with this solution:

1) Select an arbitrary node as the root of r, form a tree. For each subtree in this tree, calculate the number of nodes in the subtree (sheets - single - node -trees).

As an example for this tree

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

the result will be

  9 / | \ 5 1 2 / \ \ 1 3 1 / \ 1 1 

2) Calculate the sum of the distances for this selected root. For example, if you select vertex 1 as the root, the sum of the distances is 0 + 1 + 1 + 1 + 2 + 2 + 2 + 3 + 3 = 15

3) Turn the tree to the search depth method . For example, starting from vertex 1, we go to vertex 4. Note that for 7 nodes (1,2,3,5,6,8,9) we get further by 1 (add 7 = 9-2 to the estimate), for the other 2 (4.7), we approach 1 (subtract 2). This gives the sum of the distances equal to 15+ (9-2) -2 = 20.

Suppose we go further from 4 to 7. Now we get the sum of the distances equal to 20+ (9-1) -1 = 27 (then following from 8 vertices and approaching 1 vertex).

As another example, if we go from 1 to 2, we get the sum of the distances equal to 15+ (9-5) -5 = 14. Vertex 2 is actually the solution for this example.

This will be my algorithm.

Answer 2

Each edge e = {a, b} has the following properties:

• a_count = number of nodes per side (including a)
• b_count = number of nodes on side b (including b)
• a_sum = sum of distances from a to its subtree nodes
• b_sum = sum of the distances from b to its subtree nodes

a_count for node e = {a, b} can be estimated as follows: * get all edges of a, not counting e, sum them a_count * add 1 to the sum

a_sum for node e = {a, b} can be estimated as follows: * get all edges of a, not counting e, sum them a_sum * add a_count (it includes +1 for each enumerated edge and +1 for a)

You can freely perform calculations in a recursive function that takes node and direction parameters, storing the results in a global array.

If you run this function on each edge of the tree in both directions, you get a complete calculation for the edges. The total time for all calculations is O (n), because as soon as you go to some subtree, the recursive character closes the entire subtree in this direction, and the next calls will receive the result from the global array, and you will only make 2 * n calls for your function

With a node, the final measure is the sum of all B_count + B_sum of all the edges associated with the node. Perform one assessment of this assessment on the nodes and select the node with the minimum value.