给定一个有向图,我需要找到从中可以得出所有其他顶点的最小顶点集。
因此,函数的结果应该是最小数量的顶点,通过遵循有向边可以从中获得所有其他顶点。
可能的最大结果是没有边缘,因此将返回所有节点。
如果图形中有周期,则为每个周期选择一个节点。哪一个无关紧要,但是如果再次运行该算法,则应该保持一致。
我不确定是否存在现有的算法吗?如果有,它有名字吗?我已经尝试进行研究,而最接近的事情似乎是找到母顶点。 如果是该算法,那么可以详细说明实际算法,因为该链接中给出的答案有点含糊。
鉴于我必须在javascript中实现此功能,因此首选项将是.js库或javascript示例代码。