Geek Answers Handbook

Minimal addition to a strongly connected graph

I have a set of nodes and many directed edges between them. The edges are weightless.

How can I find the minimum number of edges that need to be added in order to make the graph strongly connected (i.e. there must be a path from each node to all the others)? Does this problem have a name?

+6
source share
3 answers

This is truly a classic graph task.

  • Run the algorithm like the Tarjan-SCC algorithm, find all the SCC. Considering each SCC as a new vertex connects the edge between these new vertices in accordance with the start graph, we can get a new graph. Obviously, the new graph is an acyclic graph with direct access (DAG).
  • In the DAG, find all the vertices whose degree is 0, define them {ICS}; find all the vertices with degree 0, define {Y}.
  • If the DAG has only one vertex, the answer is 0; otherwise the answer is max (| X |, | Y |).
+14
source

From the top of my head it seems that the simplest (smallest edges) way to get a connected graph is strongly related to just having a loop that includes all nodes; therefore, the minimum number of edges will be just N, where N is the number of nodes. If there are already edges, just do something like connecting the longest existing directional path to the next longest path, which will not overlap with your current path until you form a complete loop (as soon as your path contains all the nodes, connect the ends, to form a loop.)

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

+1
source

I would find all loosely coupled components and bundle them in a loop.

EDIT:

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

+1
source

More articles:


All Articles