请求设计求解有向图最小规模生成器的算法

问题定义 #

这个问题和咱们熟悉的「寻找能到达所有节点的最小顶点集」有点像，但核心规则不一样——一个节点必须在它所有前驱节点都被“到达”之后，自身才算被到达。

更正式地说：

• 设S是有向图G的节点子集，节点n能从S被“到达”的条件是：要么n本身就在S里，要么n的所有前驱节点都能从S被到达。
• 如果G中所有节点都能从S被到达，那S就叫做G的生成器。
• 可以确定的是，每个图都一定存在生成器（比如包含所有节点的集合肯定有效），我们的目标就是找到规模最小的那个生成器。

示例理解 #

拿一个具体的有向图来举例：

• 集合{1,3,6}是一个有效的生成器：单独的{1}可以解锁节点2，{2,3}一起能解锁节点5，而{1,3,6}配合起来就能解锁节点4。
• 但如果选S={1,5}，节点3、4、6都无法被到达，所以这不是一个生成器。
• 这里还能总结出一个关键性质：如果S是生成器，那么图中的每个环都至少包含一个S里的节点。

备注：内容来源于stack exchange，提问作者contrapunctus