algorithm - 构造一个有效的最小生成树，使得 G 中给定的顶点子集是叶子 + 证明

Question

我正在尝试设计一种算法，其中给定一个连接的加权图 G = (V, E) 和 V 中的顶点 U 的子集，将构造一个最小生成树，使得 U 中的所有顶点都是叶子（其他顶点可能也可以是叶子），或者返回不存在这样的树（假）。

这就是我所得到的，适应 Prim 的算法（公平警告，它真的很糟糕；甚至不知道它是否有效/有效或使用什么数据结构，我会接受任何其他正确的算法）：

Let x be an arbitrary node in G
Set S = {x}
While S != V:
    Let (u,v) be the cheapest edge with u in S and v not in S
    Add (u,v) to tree T if u is not in U, add v to S

If all u in U is in the tree T:
    return T
Else:
    return False

我也有一张我认为它会对我画的这张图做些什么的图片： 图片在这里

证明该算法是正确的也会让我高枕无忧。

Answer 1

如果解决方案中的所有顶点u ∈ U都是叶子，则在该解决方案中不能使用no u来连接其他两个顶点。不在其中的所有顶点U必须由不与任何 关联的边连接u。

移除U所有与 相关的边U。找到最小生成树，然后u通过从我们删除的那些中可用的最小加权边将每个树连接到树。