algorithm - 树中的最小成本边缘删除以分离树中的所有叶子

Question

这是一个更大的问题，我归结为以下问题。给定一个具有正边权重的加权树，并且有 k 个叶子。叶子是在树中恰好有一个相邻节点的节点。我需要从树中删除一些边，以便树分成 k 个组件，每个组件都包含原始树中的一个叶节点。换句话说，我需要删除边，以便原始树中的所有叶子都与原始树的所有其他叶子分开/断开。

我需要这样做，以使已删除边的权重（成本）之和最小化。证明需要删除 k-1 条边是微不足道的。所以我需要最小化这些 k-1 边的权重之和。

执行此操作的最佳方法是什么？任何提示将不胜感激。谢谢！

Answer 1

我认为贪心算法在这里有效。

即删除生成新分量的最低权重边并重复k-1次。

请注意，您必须小心以下图表：

D<-A->B->C

如果先删除 B->C，那么删除 A->B 并不会生成新的组件，因为 B 不是叶子，所以不需要分离。

换句话说，在选择权重最低的边时，不要包括任何仍不通向叶节点的边。