构造一个最小生成树覆盖的顶点的特定子集 [英] Construct a minimum spanning tree covering a specific subset of the vertices

问题描述

我有一个无向，正边重图的（V，E）的对，我希望有一个最小生成树覆盖的一个子集的 K 的顶点的 V 的。

我不限制生成树的大小的 K 的顶点;而我很清楚的这的* K *顶点必须包含在MST。

从整个MST开始，我可以削减下来的边缘/节点，直到我得到的最小生成树包含所有的 K 的。

我可以用Prim算法来获取整个MST，并开始删除边/节点，而子集k的MST不被破坏;作为选择，我可以用弗洛伊德 - 沃肖尔获得全对的最短路径，并以某种方式联合的路径。有没有更好的方式来处理呢？

解决方案

我建议你做到以下几点：

1. 创建图表的副本。
2. 虽然有边缘留在图中，这是不中的 K 的
   1. 删除任意顶点的 v 的这是不是在 K 的
   2. 对于所有对的（A，B）的邻居的 v 的
      1. 添加一条边的（A，B）的体重的重量（（A，V））+重量（（V，B））的
3. 运行普里姆对所得到的图形算法。

的直觉是，我们短路不是的 K 的顶点，其连接的到的节点。通过任何这样的节点去，成本的 v 的是从第一个节点要的 v 的加的从 v 的去成本的成本第二个节点。

该MST的结果图，将最小生成树覆盖的 K 的顶点在原图。

请注意，如果您有多个节点的 V 的，但不是在的 K 的，那么你可能有相当多的吹胀的边数。地块的边缘将presumably是多余不过，所以有可能是空间优化的一些...

相关问题：

• K-最小生成树（NP难！）

I have an undirected, positive-edge-weight graph (V,E) for which I want a minimum spanning tree covering a subset k of vertices V.

I'm not limiting the size of the spanning tree to k vertices; rather I know exactly which *k* vertices must be included in the MST.

Starting from the entire MST I could pare down edges/nodes until I get the smallest MST that contains all k.

I can use Prim's algorithm to get the entire MST, and start deleting edges/nodes while the MST of subset k is not destroyed; alternatively I can use Floyd-Warshall to get all-pairs shortest paths and somehow union the paths. Are there better ways to approach this?

解决方案

I suggest you do the following:

1. Create a copy of the graph.
2. While there are edges left in the graph, which are not in k
   1. Remove an arbitrary vertex v which is not in k
   2. For all pairs (a,b) of neighbors of v
      1. Add an edge (a, b) with weight Weight((a,v)) + Weight((v,b))

3. Run Prim's algorithm on the resulting graph.

The intuition is that we "short-circuit" the nodes which are connected through a vertex not in k. The cost of going via any such node, v is the cost of going from the first node to v plus the cost of going from v to the second node.

The MST in the resulting graph, will be the minimum spanning tree covering the vertices in k in the original graph.

Note that if you have many nodes in V but not in k, then you may have quite a blow-up in the number of edges. Lot's of edges will presumably be redundant however, so there's probably room for some optimizations...

Related problem:

• K-minimum spanning tree (NP-hard!)

这篇关于构造一个最小生成树覆盖的顶点的特定子集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！