最小添加到强连通图 [英] Minimal addition to strongly connected graph

问题描述

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

I have a set of nodes and set of directed edges between them. The edges have no weight.

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

How can I found minimal number of edges which has to be added to make the graph strongly connected (ie. there should be a path from every node to all others)? Does this problem have a name?

推荐答案

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

It's a really classical graph problem.

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

1. Run algorithm like Tarjan-SCC algorithm to find all SCCs. Consider each SCC as a new vertice, link a edge between these new vertices according to the origin graph, we can get a new graph. Obviously, the new graph is a Directed Acyclic Graph(DAG).
2. In the DAG, find all vertices whose in-degree is 0, we define them {X}; find all vertices whose out-degree is 0, we define them {Y}.
3. If DAG has only one vertice, the answer is 0; otherwise, the answer is max(|X|, |Y|).

这篇关于最小添加到强连通图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！