我正在努力寻找基于节点提取子图的方法。。我们有一个大的图（有向或无向），我们有一份节点列表，我们想从图中提取，但我们也想提取中间节点。。。
当我们研究基于2个节点的子图提取时，问题很容易。。。我们可以决定是提取这两个节点之间的所有简单路径中的所有中间节点，还是只提取最短路径中的中间节点。。。
但是如果要提取的节点超过2个呢。。。如何处理这个问题？
我很难找到任何关于这样一个问题的出版物。。。可能是因为我不知道它的确切名字。（如果它真的出现在图论问题中）
正如Jan所评论的，问题并不是具体的目标是什么
若要最小化树的权重问题，则称为广义施泰纳树。
如果你想在这些节点之间建立任何类型的生成树，你可以在图上建立最小生成树，其中有一组你想连接的节点，以及用最短路径连接每对节点的边。这是一个完整的图，创建成本很高。我认为可以通过同时从每个节点扩散来加快速度，当两个"气泡"第一次接触时，可以在这两个点之间创建路径（相同的最短路径）。将逐步连接所有节点。可能有一些路径重叠，可以用来缩短树。