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?

回答1:

It's a really classical graph problem.

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|).

回答2:

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.

回答3:

I would find all weakly connected components, and tie them up in a cycle.

EDIT:

To be more explicit, the idea is if you have WCCs W(1),...,W(n), make all of W(i%n + 1) reachable from any node in W(i), for i=1 to n.