Understanding the Mother Vertex in a Directed Graph

A mother vertex in a directed graph is characterized by its ability to reach every other vertex in the graph through a directed path. Identifying such a vertex can be crucial for understanding graph connectivity and structure. In this article, we will delve into a method to find a mother vertex in a directed graph using an efficient approach with a time complexity of $O(n + m)$, where $n$ is the number of vertices and $m$ is the number of edges.

Concepts and Definitions

1. Directed Graph: A set of vertices connected by edges, where the direction of the edge indicates the path.
2. Mother Vertex: A vertex `$v$\ is a mother vertex if there is a path from $``v$` to every other vertex in the graph.

Algorithm to find the Mother Vertex

To find a mother vertex in linear time using Depth-First Search (DFS), we can follow these steps:

1. Identify a Potential Mother Vertex:
   • Perform a DFS traversal of the graph while keeping track of the last finished vertex. The idea here is that a mother vertex is always among the last completed vertices in DFS of the original graph. This is because, if we start from a mother vertex, DFS should visit all vertices in the graph.
2. Verify the Potential Mother Vertex:
   • Conduct another DFS starting from the last finished vertex from step 1. If this DFS visits all vertices, then it is a mother vertex. Otherwise, no mother vertex exists in the graph.

Here's a detailed breakdown of the process:

Steps and Explanation

Step 1: Identify a Candidate Mother Vertex

1. Initialize a boolean array `visited[]` to keep track of visited vertices.
2. Perform DFS for each unvisited vertex. Track the last vertex that finishes processing in a variable, say `lastFinish`.

• 0 -> 2
• 2 -> 3
• 3 -> 1
• 1 -> 4
• Why Last Finish is Important: If any vertex can reach all others, a DFS from this vertex would finish processing last. Therefore, tracking the last finished vertex potentially reduces unnecessary checks.
• Graph Representation: The adjacency list representation is generally preferred for sparse graphs, contributing to the efficiency of DFS.