图中节点的拓扑排序子集

Question

我有一个大图，它代表一组依赖关系。 用户可以指定他们想要使用一定数量的这些依赖项，我需要找出使用它们的正确顺序（他们可以指定不直接相关的依赖节点，但通过图中的其他节点依赖

）。

目前，我正在通过运行图形的拓扑排序并在用户指定的所有节点都已排序后停止来实现这一点。 但是，这不会产生所需的最小依赖项，我必须返回并尝试删除任何不需要的节点。

是否有更好的方法来执行此操作或已知的算法来查找节点子集的拓扑排序？

Answer 1

最佳解决方案可能是仅构建用户选择的节点的新图，并适当分配依赖项。例如，如果 A-->B-->C，用户选择 A 和 C，则构造的图形为 A-->C。然后执行标准的拓扑排序。