algorithm - 具有多个根顶点的图中的最小生成树

Question

我想知道是否有一种算法可以在给定所有这些根顶点之间的一组根顶点的有向图中计算最小生成树(最佳分支)，但不仅是一个根顶点和所有其他顶点在图表中。

给定一组根顶点[1,4,6]和如下图所示的图G:

...该算法应该在同一张图片上返回类似绿色子图的内容。

我想得到这样一个连接所有提供给算法的根顶点的MST。我倾向于认为潜在算法的结果是图 G 的子图，它包含所有根顶点和来自 G 的一些其他顶点。

注意事项:

1. 我知道有向图没有 MST，但是有 Chu–Liu/Edmonds algorithm .
2. 我猜想这种算法的结果(如果确实可行的话)将返回一个最佳分支，其中包括图形的一些顶点以及所有根顶点。

Answer 1

最小生成树应该跨越所有顶点。我认为您实际上可能正在处理 Steiner Tree问题，因为您只需要连接其中的一个子集。不幸的是，具有无向边的传统 Steiner 树问题已经是 NP 完全问题，因此您面前的道路很艰难。