2

假设我有一个加权无向图 G = (V,E)。每个顶点都有一个元素列表。

我们从顶点根开始，开始寻找所有出现的具有值x的元素。我们希望通过最少的距离（就边权重而言）来发现所有出现的具有值x的元素。

按照我的想法，MST 将包含所有顶点（以及因此满足我们条件的所有顶点）。因此，揭示所有事件的算法可以通过找到从根到所有其他顶点的最短路径来完成（当然这将在 MST 上完成）。

编辑：正如路易斯指出的那样，如果任意选择根，MST 将不会在所有情况下都起作用。但是，为了清楚起见，根是输入的一部分，因此可能只有一个 MST（假设边缘具有不同的权重）。这个生成树实际上将具有从根开始到图中所有其他顶点的所有最小成本路径。

4

4 回答 4

4

我认为这行不通。考虑以下示例：

 x
 |
 3
 |
 y--3--root
 |     /
 5    3
 |   /
 |  /
  x

最小生成树包含权重为 3 的所有三个边，但这显然不是最佳解决方案。

如果我正确理解了这个问题，你想在图中找到包含所有标记为 x 的顶点的最小权重树。（也就是说，正确答案的总权重为 8，并且是该图中垂直绘制的两条边。）但这根本不包括您任意选择的根。

我非常有信心 Prim 算法的以下变体会起作用。不过，不确定它是否是最佳的。

假设我们要查找的标签称为 L。

  1. 使用全对最短路径算法计算所有 v, w 的 d(v, w)。
  2. 选择一些标记为 L 的节点；称之为根。（我们可以确定这将在结果树中，因为我们包括所有标记为 L 的节点。）
  3. 初始化一个优先级队列，将根初始化为 0。（优先级队列将包含标记为 L 的顶点，以及它们与树中任何节点的最小距离，包括未标记为 L 的顶点。）
  4. 当优先级队列非空时，请执行以下操作：
    1. 挑选出队列中的顶部顶点；称它为 v，它与树的距离为 d。
    2. 对于从 v 到树的路径上的每个顶点 w，包括 v，找到离 w 最近的 L 标记节点 x，并将 x 添加到优先级队列中，或更新其优先级。将 w 添加到树中。
于 2011-11-17T02:05:11.743 回答
1

答案是否定的，如果我理解正确的话。找到最小生成树将包含所有顶点 V，但您只想找到值为x的顶点。因此，您的 MST 结果可能包含不需要的顶点，增加了额外的路径长度，因此不是最佳的。

于 2011-11-17T03:02:57.483 回答
0

给出了一个示例，其中来自 Root 的 MST M1 与包含所有x节点但不包含 Root 的 MST M2 不同。

这是一个根在两个 MST 中的示例：让图 G 包含节点 R、S、T、U、V（R=Root）和顺时针路径 RSTUVR，边权重为 1、1、3、2、2 顺时针方向, 和x在 R、S、T、U 处。第一个 MST M1 将具有低于 R 的子树 ST 和 VU，成本 6 = 2+4，成本为 3 的边 TU 不包含在 M1 中。但是 M2 有子树 STU（仅）低于 R，成本为 5。

于 2011-11-17T05:28:29.557 回答
0

消极的。如果想法是为每个包含“x”的节点找到从根到它的单独路径，并最小化路径的总成本，那么您可以对从根开始的每个节点分别使用简单的最短路径计算，并将路径放在一起。

其中一些最短路径将不在最小生成树中，因此如果这是您的目标，则 MST 解决方案不起作用。MST 优化树的成本，而不是从根到节点的路径成本总和。

如果您的想法是找到一条从根开始并遍历所有包含“x”的节点的路径，那么这就是旅行商问题，它是一个 NP 完全优化问题，即非常困难。

于 2011-11-17T05:52:08.330 回答