使用包含给定节点集的节点数量最少的图确定包含附加条件的节点图

Question

我有一个未加权的有向图，其中可能有也可能没有循环。现在给定一组节点，我需要返回一个具有给定节点和最少数量节点的图形，以便它们连接。我无法创造新的边缘，所以我需要使用现有的边缘。

希望这些照片说清楚。与图开始，

比方说，我们希望有节点C，F和G的图形，该函数将返回该图

然而，有一个条件。每个边都有一个名为required的布尔变量。如果设置为true，则此边和相应的节点也需要包含在图中。

这里是另一张图片来说明 黑边不是必需的，但红色的是必需的 假设我们给出了一个和c作为包含的节点。

因此，而不是返回图是A-> C， 它将返回这个

为了使点更清楚，如果我们想与B的图和c，它也会返回该图，因为该边是必需的。

如何才能返回此图？我不希望有一个循环返回的图形，但我意识到这并不总是可行的，因为循环的边缘可能全部被标记为需要。

我最初的想法是将图形的副本保留在所需的边上，然后试图将不相交的图形拼接在一起。但是，在我将所有图形拼凑在一起的尝试中，我能够找到一个反例来表明这不是最小图。

Answer 1

在第一个例子中，您的预期输出是否包含节点e，其中所有其他节点都可以到达？或者你的意思是弱连通性（意思是边的方向无关紧要）？我想第二个是的情况下（从A，B，C例如判断），然后就可以

1. 只是忽略该边缘被引导（线性时间），
2. contract的“必需的”边缘（线性时间），
3. 计算pairwise shortest paths关于所需点的子集（O（| V |³），但我想你可以把它推到O（r | V |²），r是所需点的数量） ，然后
4. 在要求的点上找到一个minimum spanning tree（O（r²））

这就是你想要的吗？