强连接图的最小附加

Question

我有一组节点和它们之间的有向边集.边缘没有重量.

如何找到必须添加的最小边数以使图形强连接(即应该有从每个节点到所有其他节点的路径)？这个问题有名字吗？

Answer 1

这是一个非常经典的图形问题.

1. 运行Tarjan-SCC算法等算法查找所有SCC.将每个SCC视为一个新的顶点,根据原始图链接这些新顶点之间的边,我们可以得到一个新的图.显然,新图是有向无环图(DAG).
2. 在DAG中,找到in-degree为0的所有顶点,我们定义它们{X}; 找到out-degree为0的所有顶点,我们定义它们{Y}.
3. 如果DAG只有一个顶点,则答案为0; 否则,答案是max(| X |,| Y |).