寻找跨越给定顶点子集的近似最小树的算法？

Question

给定一个加权图和图中两个顶点的子集，找到一个跨越给定子集中所有（两个）顶点的最小树减少到找到子集中两个顶点之间的最短路径，这可以有效地计算使用标准路径查找算法，例如 A^*.

但是如果我们在子集中有两个以上的顶点怎么办？如果它包含 n 个顶点怎么办？是否有一种有效的算法可以找到跨越所有这些顶点的近似最小树？

我想这个问题是寻找图中两个顶点之间的最短路径问题和寻找图的最小生成树问题的推广。

编辑： 我意识到这个问题被称为 Steiner 树问题，并且显然是 NP 完全的，所以我改变了我对算法的要求，以找到一个最小的这样的树来找到一个近似的最小树。

Answer 1

有！其实有两个:) 首先，我们需要谈谈您实际要求的是什么。您正在寻找的算法是一种为任何（相干）图找到最小生成树的算法。 MST（最小生成树）是使用所需顶点的最小权重和给出连接图中所有点的最小权重连贯树的树。这是一个例子：

如果您有兴趣，我建议您阅读维基百科文章https://en.wikipedia.org/wiki/Minimum_spanning_tree

MST 的性质很多，在图定理中本身就是一个空洞的话题。我不打算详细介绍，因为我只是想提供一些背景信息。

经常使用两种算法来解决这个问题：

1. Prims 算法 Prims 算法早在 1930 年就被 Vojtech Jarnik 首次发现，后来在 1957 年被 Prim 重新发现，并在 1959 年被我的个人偶像 Edsger W. Dijkstra 再次发现，算法被称为 Prim 或 Jarnik-Prim 或 Jarnik-Prim-Dijkstra 算法在源头上。 它使用以下伪代码创建 MST

Given : a coherent graph G(V,E) with n vertices
Result : R an MST for the graph G
Algorithm :
set R equal to a graph with one vertex and an empty set of edges
while R has less then n-1 edges repeat : 
    1) choose an edge (u,v) in E with u in R and v not in R and the weight of (u,v) being the         minimal weight of al the edges who have a start point in T but not an endpoint
    2) Add (u,v) to the edges of R together with the vertices v

这是一个可视化：

2) Kuskal 算法：另一种鲜为人知的算法是 Kruskal 算法。它实现了与 Prim 算法完全相同的东西，但它是不变延迟的，伪代码如下：

    Given : a coherent graph G(V,E) with n vertices
    Result : R an MST for the graph G
    Make R a graph with an empty set of vertices an edges
    while R has less then n-1 edges repeat :
        1) take (u,v) the least weighted edge that does not make a circle in R
        2) add (u,v) to R ass well as their vertices
        // while adding the vertices you shouldnt keep doubles ofcourse

这是一个可视化：

与 Prim 算法的不同之处在于，Kruskal 算法并非始终具有连贯的图。这在 Kruskal 算法的不变量中也没有指定。这是两种算法正确性证明的链接：

1. 初级： https://home.uncg.edu/cmp/faculty/srtate/330.f16/primsproof.pdf
2. 克鲁斯卡尔： http://people.qc.cuny.edu/faculty/christopher.hanusa/courses/634sp12/Documents/KruskalProof.pdf

希望这能回答您的问题。