Question

Give an efficient algorithm which takes as input a directed graph $\mathbf{G}\left(V,E\right)$and determines whether or not there is a vertex$\mathbf{s}\mathbf{\in }\mathbf{V}$ from which all other vertices are reachable.

Short answer

Algorithm takes as input a directed graph G(V,E) and determines whether or not there is a vertex$\mathrm{s}\in \mathrm{V}$from which all other vertices are reachable is proved.

Step-by-step solution

Explain the algorithm for determining a vertex s∈V from which all the vertices are reachable.

A vertex s belongs to $\mathbf{G}\left(V,E\right)$ where v is the vertex and e is the edges such that all other vertices are reachable from the vertex s and this vertex s is known as mother vertex. And there may be more than one mother vertex present in the graph.

In other words, it states that all other vertices in G are reached by a path from v. Kosaraju's algorithm is used to find strongly connected component in the graph.

Determine the mother vertex.

In an undirected graph, here all vertices are act as a mother vertex because from each vertex makes their path towards its every other vertex.

Or to finding the mother vertex in any directed graph here, check all vertices of the given graph and detect from which vertex every other node are connected.

Let a directed graph which contain nine edges and seven vertices. In this graph node 5 is act as a mother vertex from which all other vertices are reachable. For example, the graph is given below:

5is the mother vertex in directed graph.

Here in this graph from vertex five all other vertices are reachable. From $5\to 2$by one vertex in the middle that is 2. From$5\to 4$by follow the directions from $5\to 6\to 4$.

From $5\to 3$by following the path that is$5\to 6\to 4\to 1\to 3$there is the direct path from $5\to 2$and at the last from $5\to 1$path is $5\to 6\to 0\to 1$.

 A directed graph with mother vertices.

Another example is given as the directed graph which contain five edges and five vertices 0,1,2,3,4,5. In this graph node 0, 1 and 2 are act as a mother vertex from which all other vertices are reachable.

From vertices 0,1,2, all other vertices are reachable. From 0 to 1, consider 2 as a middle vertex. Like that from zero all the other vertices are visited. Then from 1 to 3, consider 0 as a middle vertex. Like that from 0, all the other vertices are reachable same as by the mother node 2.

Hence,thealgorithm that determines whether or not there is a vertex$\mathrm{s}\in \mathrm{V}$from which all other vertices are reachable is proved.