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