graph - 在有向图中查找包含特定节点的路径

Question

我有一个有向图，以及该图的一组 U 节点。我想知道是否存在包含集合 U 中所有节点的路径（不一定是简单路径）。最有效的方法是什么？

Answer 1

提示：用 e \in E' 创建一个图 G'=(U,E') 如果 e 的目标可以从原始图 G 中的 e 的源到达。（可达性的精确计算取决于您是否允许访问节点两次。）

现在，为了解决您的问题，您必须检查什么 G'？