Minimum number of edges to be added so that one can reach all vertices from root?

Question

Here 1 is the root by adding edge from 1 to 3 and 2 to 4 one can reach all vertices from 1. What's the algorithm for achieving this?

Answer 1

As with most problems on reachability in directed graphs, this should be solved in two steps:

1. Solve the problem in an acyclic graph.
2. Apply the solution in step 1 to the condensation of the graph: the directed acyclic graph obtained by replacing each strongly connected component by a single vertex.

---

Suppose first that our directed graph has no cycles. (For this purpose, we ignore edges into the desired root vertex; if they exist, we pretend they don't, because they will never help us.)

Every vertex in the directed graph is reachable from some vertex of indegree $0$: just follow edges backward arbitrarily until you reach such a vertex. (Because the graph is acyclic, we will never repeat vertices in this process, so it must end eventually - and it can only end when we reach a vertex of indegree $0$.) Therefore it's enough to add edges from the desired root to every other vertex of indegree $0$.

On the other hand, that's also an optimal solution: we need to add some edge to every such vertex, otherwise they will not be reachable from anywhere else.

So in this case, the minimum number of edges is just the minimum number of indegree-$0$ vertices, ignoring the vertex that will be our root.

(This is the situation in the example in the question: vertices $3$ and $4$ have indegree $0$, and if we add edges $1 \to 3$ and $1 \to 4$, then all vertices are reachable from vertex $1$.)

---

In a graph with cycles, this is not necessarily true. Consider a graph with vertices $\{1,2,3,4\}$ and edges $\{2 \to 3, 3 \to 4, 4 \to 2\}$. If we want every vertex to be reachable from $1$, we need to add an edge, even though no other vertices have indegree $0$.

The solution is to take the condensation: replace every strongly connected component by a single vertex. We do this because if we can reach one vertex in a strongly connected component, we can reach them all (by definition, any vertex in a strongly connected component can reach any other).

The condensation is a directed acyclic graph, so the solution from our previous section applies to it.

A way to summarize the combination of solutions is: the minimum number of edges we need is the number of strongly connected components, other than the strongly connected component containing our desired root, which are not reachable from outside the strongly connected component. (In the condensation, these are exactly the strongly connected components which will have indegree $0$.)

A solution that achieves this just adds one arbitrary edge from the desired root to each of the strongly connected components we counted.