我有一个带有未加权边的无向连通图。如何构建生成树（解决方案可能不是唯一的），以使所有节点的深度总和最小化？这显然没有找到最小生成树，因为边缘的“权重”实际上取决于孩子的深度。
我认为，给定一个指定的根，深度总和最小的树可以通过以广度优先顺序贪婪地将所有可以连接的子节点连接到每个节点来形成。因此，我将通过应用相同的过程 N 次来找到总深度最小的树，将 N 个节点中的每一个指定为根，并在 N 个候选者中选择最小的一个。这是一个有效的算法吗？请指出它是否错误，或者是否存在更有效的方法。
问问题
1208 次
1 回答
3
这是一个有效的算法吗？
是的，算法是正确的。
给定一个R要被认为是生成树根的节点，该节点在生成树中的深度至少是图中从到到N的最短路径的长度，所以深度之和至少是和最短路径的长度（从）。RNR
该算法构建的树将每个节点R与最短路径之一连接起来，因此深度的总和就是距离的总和，我们在上面看到是一个下限。
作为一个小的优化，如果节点数至少为 3，则不需要将度数为 1 的节点视为树的根。（对于R以度为 1 的节点为根的树，考虑相同的图，将其视为以R的邻居为根的树。深度R增加 1，所有其他节点的深度减少 1，因此深度总和减少由number_of_nodes - 2.)
于 2013-02-21T19:29:11.640 回答