构造一棵高效的最小生成树，使得 G 中给定的顶点子集是叶子 + 证明
Construct an efficient, minimum spanning tree such that given subset of vertices in G are leaves + proof
我正在尝试设计一种算法，其中，给定一个连接的加权图 G = (V, E) 和 V 中的顶点 U 的子集，将构造一个最小生成树，使得 U 中的所有顶点都是叶子（其他顶点也可能是叶子），或者 returns 不存在这样的树 (False)。
这就是我得到的全部，改编 Prim 的算法（公平警告，它真的很糟糕；甚至不知道它 works/is 是否有效或使用什么数据结构，我会接受 字面上 任何其他正确的算法代替）：
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
我也有一张图片，我认为它会对我画的这张图产生什么影响：
pic here
算法正确的证明也会让我安心。
如果所有顶点 u ∈ U 都将成为解决方案中的叶子，则 no u 可以在该解决方案中用于连接其他两个顶点。不在 U 中的所有顶点必须由不属于任何 u.
的边连接
删除 U 和 U 的所有边缘。找到最小生成树，然后通过我们移除的可用 smallest-weighted 边将每个 u 连接到树。
我正在尝试设计一种算法，其中，给定一个连接的加权图 G = (V, E) 和 V 中的顶点 U 的子集，将构造一个最小生成树，使得 U 中的所有顶点都是叶子（其他顶点也可能是叶子），或者 returns 不存在这样的树 (False)。
这就是我得到的全部，改编 Prim 的算法（公平警告，它真的很糟糕；甚至不知道它 works/is 是否有效或使用什么数据结构，我会接受 字面上 任何其他正确的算法代替）：
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
我也有一张图片，我认为它会对我画的这张图产生什么影响： pic here
算法正确的证明也会让我安心。
如果所有顶点 u ∈ U 都将成为解决方案中的叶子，则 no u 可以在该解决方案中用于连接其他两个顶点。不在 U 中的所有顶点必须由不属于任何 u.
删除 U 和 U 的所有边缘。找到最小生成树，然后通过我们移除的可用 smallest-weighted 边将每个 u 连接到树。