algorithm - 对强连通图的最小添加

Question

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

我怎样才能找到最少数量的边，必须添加这些边才能使图强连通(即，从每个节点到所有其他节点都应该有一条路径)？这个问题有名字吗？

Answer 1

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

1. 运行类似 Tarjan-SCC 算法的算法以找到所有 SCC。考虑每个 SCC 作为一个新的顶点，在这些新的之间连接一条边根据原始图的顶点，我们可以得到一个新的图。显然，新图是有向无环图(DAG)。
2. 在DAG中，找到入度为0的所有顶点，我们定义它们{X};找到出度为 0 的所有顶点，我们定义他们{Y}。
3. 如果DAG只有一个顶点，则答案为0；否则，答案是最大值(|X|，|Y|)。