具有多个根顶点的图中的最小生成树
我想知道是否有一种算法可以计算有向图中的最小生成树（最佳分支），给定所有这些根顶点之间的一组根顶点，但不仅仅是一个根顶点和图中的所有其他顶点。
给定一组根顶点 [1,4,6] 和一个图 G，如下图所示：
...算法应该返回类似同一张图片上的绿色子图的内容。
我想要得到这样一个 MST，它连接提供给算法的所有根顶点。我倾向于认为算法的结果是图 G 的子图，其中包含 G 的所有根顶点和其他一些顶点。
注意：
- 我知道有向图没有 MST，但是有是 Chu–Liu/Edmonds 算法。
- 我猜想这种算法的结果（如果实际上可能的话）将返回最佳分支，其中包括图的一些顶点以及所有根顶点。
I would like to know if there is an algorithm which computes a minimum spanning tree (optimum branching) in a directed graph given a set of root vertices between all of these root vertices, but not only one root vertex and all other vertices in a graph.
Given a set of root vertices [1,4,6] and a graph G like the one on the following picture:
...the algorighm should return something like a green sub-graph on the same picture.
I would like to get such an MST that connects all the root vertices provided to the algorithm. I tend to think that the result of the would-be algorithm is a sub-graph of the graph G which contains all root vertices and some other vertices from G.
Notes:
- I know that there is no MST for a directed graph, but there is Chu–Liu/Edmonds algorithm.
- I guess that a result of such an algorithm (if it is actually possible) will return an optimum branching, which includes some vertices of a graph along with all root vertices.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
最小生成树应该跨越所有顶点。我认为您可能实际上正在处理 Steiner Tree 问题，因为您只需要连接其中的一个子集。不幸的是，具有无向边的传统斯坦纳树问题已经是 NP 完全问题，所以你前面的路很艰难。
Minimum Spanning Trees are supposed to span all the vertices. I think you might be actually dealing with a Steiner Tree problem, given that you only need to connect a subset of them. Unfortunately, the traditional Steiner tree problem with undirected edges is already NP complete so you have a tough road ahead of you.