我有一个未加权的有向图，其中可能有也可能没有周期。现在给定一组节点，我需要返回一个图，其中包含给定节点和最小数量的节点，以便它们连接起来。我无法创建新的边缘，所以我需要使用现有的边缘。
希望这些图片能说明问题。从一张图开始，
假设我们想要具有节点 c、f 和 g 的图，该函数将返回此图
但是，还有一个条件。每条边都有一个名为 required 的布尔变量。如果设置为 true，则该边和相应的节点也需要包含在图中。
这是另一张图片来说明黑色边缘不是必需的，但红色边缘是必需的假设我们给定 a 和 c 作为要包含的节点。
因此，它不会返回 A->C 的图形，而是返回这个
为了更清楚地说明这一点，如果我们想要一个带有 b 和 c 的图，它也会返回该图，因为该边是必需的。
如何返回此图？我不希望返回带有循环的图形，但我意识到这并不总是可能的，因为循环的边缘可能都被标记为所需的。
我最初的想法是制作一份保留在所需边上的图副本，然后尝试将不相交的图拼凑在一起。但是在我所有尝试将图表拼凑在一起的过程中，我找到了一个反例，表明它不是最小的图表。