如何在有向图中找到最小的顶点集，以便可以到达所有其他顶点

Question

给定一个有向图，我需要找到从中可以得出所有其他顶点的最小顶点集。

因此，函数的结果应该是最小数量的顶点，通过遵循有向边可以从中获得所有其他顶点。

可能的最大结果是没有边缘，因此将返回所有节点。

如果图形中有周期，则为每个周期选择一个节点。哪一个无关紧要，但是如果再次运行该算法，则应该保持一致。

我不确定是否存在现有的算法吗？如果有，它有名字吗？我已经尝试进行研究，而最接近的事情似乎是找到母顶点。 如果是该算法，那么可以详细说明实际算法，因为该链接中给出的答案有点含糊。

鉴于我必须在javascript中实现此功能，因此首选项将是.js库或javascript示例代码。

Answer 1

据我了解，这只是在图中找到紧密连接的组件。Kosaraju的算法是做到这一点的最巧妙的方法之一。它使用两次深度优先搜索，而后来的算法仅使用一次，但我最喜欢它的简单概念。

编辑：只是为了扩展这一点，所以找到了最少的一组顶点，如这篇文章的注释中所建议：1.找到图的强连接组件-将每个组件简化为一个顶点。2.其余图是DAG（如果存在断开连接的组件，则为DAG组），其根形成所需的顶点组。