algorithm - 如何通过访问最少数量的起始顶点来探索有向图 (DAG)？

Question

给定一个 DAG(可能不是强连接的 e.i，由几个连接的组件组成)，目标是找到访问以充分探索图形所需的起始顶点的最少数量。
我想到的一种方法是生成给定顶点的所有排列并按该顺序运行拓扑排序。回溯最少的那个就是答案。
是否有高效的算法来执行上述任务？

Answer 1

这是一个著名的问题 minimum path cover ，可惜wiki上什么都没说，你google一下就可以了。

作为methioned，最小路径覆盖问题是NP-hard在正常图中。但在 DAG 中，可以用 Matching 来解决。 .

方法:

将每个顶点u分成两个不同的顶点u1和u2。对于原始图中的每条边(u->v)，在新图中添加边(u1->v2)。然后做任何你喜欢的匹配算法。结果是n - 最大匹配，n是原始图中的顶点总数。