Given an directed acyclic graph, create a strategy so that there is a bidirectional path between all possible Vertices

Question

Given an directed acyclic graph, create a strategy so that there is a bidirectional path between all possible Vertices

You can attain this by adding edges. Propose a strategy for solving this with adding as little edges as possible A Vertice on the input graph can be without edges.

EXAMPLE: To solve this graph the most efficient way, we need to add ONLY 2 edges:

Keep in mind that the algorithm doesn't need to be perfect, also NO NEED to code anything (unless you want to:)).

Answer 1

Consider a DAG that has m vertices with in-degree 0 and n vertices with out-degree 0:

Obviously, you will need to add m edges incoming to the in-degree 0 vertices, and n edges outgoing from the out-degree 0 vertices, so the best you can hope for is max(m,n) new edges. We can achieve this.

First, if m > n, then connect in-degree 0 vertices until m = n. Otherwise connect out-degree 0 vertices until m = n.

Now we have m=n, which we will maintain:

• Find a vertex with in-degree 0 that doesn't reach all the vertices with out-degree 0. If there isn't one, then connect out-degree 0 vertices arbitrarily to in-degree 0 vertices and you're all done.
• Otherwise, connect an out-degree 0 vertex that it does reach to an in-degree 0 vertex that reaches an out-degree 0 vertex that it doesn't reach. This reduces m and n by 1.
• Repeat until you're done.