求有向图中其他顶点可到达的最小顶点数

Question

在有向图中，我想在一些顶点上调用bfs，以便满足所有顶点。

(换句话说，所有其他顶点都可以从这些选定的顶点到达。)

我想找到这样的顶点的最小数量。

事实上，这个问题出现在社交网络中，当我们想找到最小数量的人时，如果我们向他们发送消息，那么所有网络成员都会收到。(假设我们知道当有人收到信息时，他/她会把信息发送给所有的追随者。)

有人能帮忙吗？

Answer 1

对于没有循环的图(即非循环图)，这将很容易。所有没有传入边的节点都将是最佳解决方案。因为所有其他节点都应该可以从其中一个节点访问。

对于具有循环的图，首先找到强连通分量，然后得到一个非循环图。上述方法再次有效。