16

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

我怎样才能找到必须添加以使图形强连接的最少边数（即，应该有从每个节点到所有其他节点的路径）？这个问题有名字吗？

4

3 回答 3

29

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

  1. 运行类似 Tarjan-SCC 算法的算法来查找所有 SCC。将每个 SCC 视为一个新顶点，根据原图在这些新顶点之间连接一条边，就可以得到一个新图。显然，新图是有向无环图（DAG）。
  2. 在DAG中，找到所有入度为0的顶点，我们定义它们为{X}；找到所有出度为0的顶点，我们定义它们{Y}。
  3. 如果 DAG 只有一个顶点，则答案为 0；否则，答案是 max(|X|, |Y|)。
于 2013-01-14T12:20:43.450 回答
1

Off the top of my head, it seems the simplest (fewest edges) way to make a directed graph strongly connected would be to just have a cycle involving all nodes; so the minimum number of edges would just be N where N is the number of nodes. If there are already edges, just do something like connect longest existing directed path to the next longest path that doesn't overlap with your current path, until you form a complete cycle (once your path contains all nodes, connect the ends to form the cycle.)

Not sure if there is a more formal definition of any of this, but is seems logical to me.

于 2013-01-13T16:11:45.173 回答
1

我会找到所有弱连接的组件，并将它们捆绑在一个循环中。

编辑：

更明确地说，这个想法是，如果您有 WCC W(1),...,W(n)，则可以从, forW(i%n + 1)中的任何节点访问所有内容。W(i)i=1 to n

于 2013-01-13T19:35:20.103 回答