algorithm - 寻找最小化节点深度总和的生成树

Question

我有一个带未加权边的无向连通图。如何构建生成树(解决方案可能不是唯一的)以使所有节点的深度总和最小化？这显然不是在寻找最小生成树，因为边的“权重”实际上会根据 child 的深度而变化。

我认为，给定一个指定的根，深度总和最小的树可以通过贪婪地连接所有你可以作为子节点连接到广度优先顺序的每个节点来形成。因此，我将通过应用相同的过程 N 次，将 N 个节点中的每一个指定为根节点，并从 N 个候选节点中选择最小的一个来找到总深度最小的树。这是一个有效的算法吗？请指出是否有误，或者是否存在更有效的方法。

Answer 1

Is this a valid algorithm?

是的，算法是正确的。

给定一个节点 R 被认为是生成树的根节点，生成树中节点 N 的深度至少是图中从 R 到 N 的最短路径，所以深度之和至少是最短路径长度之和(从 R).

该算法构建的树将每个节点连接到R，其中一条是最短路径，因此深度之和就是距离之和，我们在上面看到的是一个下界。

作为一个小的优化，如果节点数至少为 3，则不需要将度数为 1 的节点视为树的根。 (对于以度为 1 的节点 R 为根的树，考虑同一个图，将其视为以 R 的邻居为根的树。R 的深度 增加 1，所有其他节点的深度减少 1，因此深度总和减少 number_of_nodes - 2。)