查找所选顶点的最小生成树的算法

Question

可以使用Prim算法或Kruskal算法来找到顶点/节点和边/链接集合的最小生成树/图.我想要的是一种算法,它可以找到该集合的最小生成图,但结果图只需要包含任意选择的节点,而不是所有节点.如果结果图包含的节点数多于所需的节点数,那也没关系.

这样的算法存在吗？在修改图形以仅包含所需节点后,也许可以使用Prim(或Kruskal)算法？但是,我不确定如何在保持连接性的同时修改图形.

例如,假设我们有一个菱形的起始图(括号中的链接成本):

    A
(2)/ \(1)
  B   C
(2)\ /(5)
    D

现在,我们任意决定只需要节点A和D. 如果我们从A开始,我们仍然希望它采用左路径,因为((2 + 2)<(1 + 5)).

假设我们稍微修改了图表:

    A
(2)/ \(1) (2)
  B   C ------E
(2)\ /(5)
    D

如果我们确定只需要节点A,D和E,我们就会发现成本最低的路径不一定是链路最少的路径.考虑A - B - D和A - C - E成本为7,但A - C - D和C - E成本为8.

Answer 1

你想要找到的是一个离散的Steiner树.当图中并非所有顶点都是强制性的,但允许树在可选顶点处分割时,问题就是NP难.

维基百科说(上面已经链接到)这个问题:相信通常不能在多项式时间内实现任意好的近似比.存在多项式时间算法,其找到最小Steiner树的因子1.39近似值.