complexity-theory - 在多根图中找到根

Question

我们处理一个有向图，它可能包含或不包含循环，并且可能连接或不连接。我们希望找到最小的顶点集，以便图中的每个其他顶点都可以从它们访问。

例如，给定：http: //i.stack.imgur.com/wtRYB.png（所以不会让我发布图片：/）

解决方案可以是 (A, E) 或 (A, F)。

我的第一种方法是寻找没有父节点（indegree = 0）的节点，但这没有考虑到上述循环。

经过快速搜索，我发现关于 SO 中的非循环有向图的内容相对较少。那么，您可以建议我的最低复杂度算法是什么？

Answer 1

第二次尝试。

这是我想到的：

令 V 为集合顶点的副本。

1. 从 V 中选择节点。以某种方式标记它
2. 当 V 有一个未标记的父级时，选择它。
3. 该过程完成后，您将只剩下一个根。请注意，它可以是循环的一部分，标记将确保过程完成。
4. 现在递归地在根的孩子之间传播删除消息。也就是说，它将命令他的孩子对他的孩子进行同样的命令，然后将自己从 V 中删除。
5. 从 V 的左边选择另一个节点；冲洗并重复。

它有效，但我不禁想知道是否有更快的方法。想法？