包含给定节点集的最小连通子图

我无法想到找到最佳解决方案的有效算法，但假设您的输入图是密集的，以下可能会运行得很好： 将输入图形

G(V, E)

转换为加权图形

G'(N, D)

，其中

N

是要覆盖的顶点子集，

D

是原始图形中相应顶点之间的距离（路径长度）。这将“折叠”您不需要的所有顶点到边缘。 计算

G'

的最小生成树。 通过以下步骤“展开”最小生成树：对于最小生成树中的每个边缘

d

，取图6中的相应路径并将路径上的所有顶点（包括端点）添加到结果集

V'

和所有边缘中。结果集的路径

E'

。 该算法很容易绊倒以提供次优解决方案。示例案例：等边三角形，其中在拐角处，在边的中点和三角形的中间存在顶点，并且沿着边的边缘以及从角的边缘到三角形的中间。为了覆盖角落，它足以选择三角形的单个中点，但是这个算法可能会选择边。尽管如此，如果图表密集，它应该可以正常工作。     

这正是众所周知的NP-hard Steiner Tree问题。如果没有关于实例的详细信息，很难就适当的算法提供建议。     

最简单的解决方案如下： a）基于mst：     - 最初，V的所有节点都在V'     - 构建图G（V，E）的最小生成树 - 称之为T.     - loop：对于T中不在N中的每个叶v，从V'中删除v。     - 重复循环直到T中的所有叶子都在N. b）另一种解决方案如下 - 基于最短路径树。     - 选择N中的任何节点，将其称为v，让v为树的根T = {v}。     - 从N中删除v。 环： 1）从T中的任何节点和N中的任何节点中选择最短路径。最短路径p：{v，...，u}其中v在T中，u在N中。  2）p中的每个节点都加到V'。  3）从N中删除p和N中的每个节点。 ---重复循环，直到N为空。 在算法开始时：使用任何已知的有效算法计算G中的所有最短路径。 就个人而言，我在我的一篇论文中使用了这个算法，但它更适合分布式环境。 设N是我们需要互连的节点集。我们想要构建图G的最小连通支配集，并且我们希望为N中的节点赋予优先级。 我们给每个节点u一个唯一的标识符id（u）。如果你在N中，我们让w（u）= 0，否则w（1）。 我们为每个节点u创建对（w（u），id（u））。 每个节点u构建一个多集中继节点。也就是说，1跳邻居的集合M（u）使得每个2跳邻居是M（u）中的至少一个节点的邻居。 [最小M（u），解决方案越好]。 如果且仅在以下情况下，你在V' 你的所有邻居中都有最小的对（w（u），id（u））。 或者在M（v）中选择u，其中v是具有最小（w（u），id（u））的u的1跳邻居。 - 以集中方式执行此算法时的技巧是在计算2跳邻居时有效。我可以从O（n ^ 3）得到的最好的是通过矩阵乘法得到O（n ^ 2.37）。 - 我真的想知道最后一个解决方案的近似值是多少。 我喜欢这个steiner树启发式的参考： 施泰纳树问题，黄禹兰; Richards Dana 1955- Winter Pawel 1952     

您可以尝试执行以下操作： 为所需节点创建最小顶点覆盖

N

。 将这些可能未连接的子图折叠成“大”节点。也就是说，对于每个子图，将其从图中删除，并将其替换为新节点。调用这组节点

N'

。 在

N'

中执行节点的最小顶点覆盖。 “解压缩”

N'

中的节点。 不确定它是否在某个特定范围内给出了近似值。你甚至可以欺骗算法做出一些非常愚蠢的决定。