How to find the ideal topological ordering (fewest steps as explained in description below)?

Question

Given a network of N computers, there are N-1 cables that connect the computers into a tree. A message is passed to computer 1 and it will propogate it to its neighbouring computers and so on until all computers in the network have received the message. Return the order in which to propagate the message such that the entire network will receive it in the shortest time possible.

For example: Given that Computer 1 connects to 2 and 3, and Computer 2 connects to 4 and 5. deal scenario takes total of 3 steps as outlined below:

Step 1: Computer 1 -> Computer 2.

Step 2: Computer1 -> Computer 3 and Computer 2-> Computer 4.

Step 3: Computer 2-> Computer 5.

Note that if we had decided to pass the message from 1 to 3 in the first step, it would have taken total 4 steps.

How do we find an optimal algorithm (not bruce force) for this problem? I get that it involves some sort of finding the ideal topological ordering, but I am not sure how to implement it in a way that is not brute force. Thanks in advance!! :D

My current solution is simply finding all topological orderings and choosing the best one out of all.

Answer 1

In a tree there exists exactly one path from the root to each vertex.

So:

• Find all the leaves ( vertices with no children )
• Order the leaves in descending order of distance from the root.
• The root must send messages to its children in the order the children are on the paths to the leaves in descending order of distance from the root.
• Every vertex that is not the root or a leaf is the root of a sub-tree. Repeat previous two steps on each sub-tree root that has more than one child.