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.

Featherston

Interesting approach. O(n^2) is pretty good, if the algorithm is valid. – Steffy

It seems valid to me. Great algorithm – Steffy

Spanning tree doesn't really have a root node, so the node depth concept isn't clear to me. Perhaps by node depth you mean the tree diameter or the depth if rooted at the first node you visited in Prim algorithm? – Byrdie

@JuanLopes Probably I should say it's also about finding a root that can minimize this... It's not related to Prim algorithm though. – Featherston

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.)

Nessim

+1, excellent answer to a great question. As a further optimization, inside each BFS, terminate early if the sum of depths is greater than the minimum found so far. For some types of graphs, looping over the vertices in descending order of degree might help too. – Pointillism

Didn't realize that it's essentially a shortest path problem. Thanks!! – Featherston