Question

for directed un-weighted graph :

Implement the following member function: int MyGraphAss3::findTopV(). This function returns a vertex that can reach all other vertices in the graph by a path starting from this vertex. There can be more than one top vertex in a graph. Just output one of them.

(in c++)

Answer 1

To implement the given member function: int MyGraphAss3::findTopV(), we will use DFS algorithm while finding a vertex that can reach all other vertices.

Note : If incase there is no top vertex in the given graph, then the following function will return -1.
int MyGraphAss3::findTopV()
{
   vector <bool> visited(V, false); //An array to keep track of visited nodes, here false indicates not visited vertices
   int v = 0; // Here v is a variable to store top vertex
   for (int i = 0; i < V; i++)
   {
       if (visited[i] == false) {//If node is not visited
           DFS(i, visited);
           v = i;
       }
   }
   fill(visited.begin(), visited.end(), false); // At this step we will reset the visited array as false
   DFS(v, visited);
   for (int i=0; i<V; i++)
       if (visited[i] == false)
           return -1;
   return v;
}

Sample output: