Solution: Find a Mother Vertex in a Directed Graph
Let's solve the Find a Mother Vertex in a Directed Graph problem.
Statement
Given a directed graph as input, determine a mother vertex within it. A mother vertex in a graph
Constraints:
graph.length
There are no repeated edges.
Solution 1: Depth-first search
To find a mother vertex in a given directed graph, we apply a depth-first search (DFS) strategy from each vertex to confirm if there’s a vertex from which all other vertices are reachable.We start by iteratively performing a depth-first search (DFS) starting from each vertex in the graph. For each vertex, we call performDFS()
to see how many vertices can be reached from it. If the number of vertices reached from the current vertex is equal to the total number of vertices in the graph, it means that the current vertex can reach all other vertices and, thus, is a mother vertex. We return this vertex index. If no vertex meets the above condition, we return -1
, indicating there’s no mother vertex in the graph.
We used a helper function, performDFS()
, to perform a depth-first search starting from a source vertex and count how many vertices are reachable from this source. It initializes a list verticesReached
to keep track of visited vertices and a MyStack()
stack to manage the DFS traversal. The source vertex is marked as visited and pushed onto the stack. While the stack is not empty, the algorithm continuously pops a vertex from the stack, and for each of its adjacent vertices:
If an adjacent vertex hasn’t been visited, it is marked as visited, pushed onto the stack, and the
verticesReached
counter is incremented.
After traversing, the function returns the count of vertices reached plus one (to include the source vertex itself).
Now, let’s look at the following illustration to get a better understanding of the solution:
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.