我想不出一种能找到最佳解决方案的高效算法，但是假设您的输入图很密集，那么下面的方法可能会很好地起作用：

1. 将输入图转换G(V, E)为加权图G'(N, D)，其中N是您要覆盖的顶点的子集，并且D是原始图中相应顶点之间的距离（路径长度）。这会将所有不需要的顶点“折叠”到边中。

2. 计算的最小生成树G'。

3. 通过以下过程“扩展”最小生成树：对于d最小生成树中的每个边缘，采用图中的相应路径，G并将路径上的所有顶点（包括端点）添加到结果集V'，并将路径中的所有边缘添加到结果集。结果集E'。

该算法很容易跳闸，给出次优的解决方案。示例情况：等边三角形，其中在角，边的中点和三角形的中间有顶点，并且沿边且从角到三角形的中间有边。为了覆盖角，选择三角形的单个中点就足够了，但是此算法可以选择边。尽管如此，如果图形密集，它应该可以正常工作。