Hsn*_*edi 3 algorithm graph social-networking
在有向图中,我想在某些顶点上调用bfs,以便满足所有顶点.
(换句话说,所有其他顶点都可以从这些选定的顶点到达.)
我想找到这样的顶点的最小数量.
实际上这个问题出现在社交网络中,当我们想要找到最小数量的人,如果我们发送消息然后所有的网络成员都会得到这个.(假设我们知道什么时候有人得到他/她将发送的消息对他/她的所有粉丝.)
有人可以帮忙吗？
Zhi*_*ang 7
对于没有循环的图形(即非循环图),它将很容易.没有入边的所有节点都是最佳解决方案.由于所有其他节点都应该可以从其中一个节点到达.
对于带循环的图形,首先找到强连通分量,然后得到非循环图形.上面的方法再次起作用.
归档时间：
12 年 前
查看次数：
1460 次
最近记录：