Finding a spanning tree that minimizes sum of nodes' depths

Question

I have an undirected connected graph with unweighted edges. How can I build a spanning tree (the solution might not be unique) such that the sum of depths of all nodes is minimized? This is obviously not finding the minimum spanning tree, as the "weight" of edges actually vary depending on the the child's depth.

I think that, given a designated root, the tree with minimum sum of depths can be formed by greedily connecting all you can connect as children, to each node in a breadth-first order. Therefore I am going to find the tree with minimum total depth by applying this same procedure N times, designating each of the N nodes as root, and choosing the minimum one among the N candidates. Is this a valid algorithm? Please point out if it is wrong, or if anything more efficient exists.

Answer 1

Is this a valid algorithm?

Yes, the algorithm is correct.

Given a node R that is to be considered the root of the spanning tree, the depth of a node N in the spanning tree is at least the length of the shortest path from R to N in the graph, so the sum of the depths is at least the sum of the lengths of the shortest paths (from R).

The tree constructed by the algorithm connects each node to R with one of the shortest paths, so the sum of the depths is the sum of the distances, which we saw above is a lower bound.

As a small optimisation, if the number of nodes is at least 3, no nodes with degree 1 need to be considered as the root of the tree. (For a tree rooted at a node R with degree 1, consider the same graph, viewed as a tree rooted at R's neighbour. The depth of R increases by 1, the depth of all other nodes decreases by 1, so the sum of depths decreases by number_of_nodes - 2.)