我有一组节点和它们之间的一组定向边。边缘没有重量。
如何找到使图强连接所需的最小边数(即,应该有一条从每个节点到所有其他节点的路径)?这个问题有名字吗?

最佳答案

这是一个非常经典的图问题。
运行tarjan-scc算法来查找所有scc。考虑
每个scc作为一个新的vertice,在这些新的
根据原点图,我们可以得到一个新的图。
显然,新图是有向无环图(dag)。
在dag中,找到度为0的所有顶点,定义它们
{x};找到所有的顶点,其out degree为0,我们定义
他们{y}。
如果dag只有一个vertice,那么答案是0;否则,答案是
是最大值(x,y)。

关于algorithm - 最小添加到强连通图,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/14305236/

10-08 22:47
查看更多