Find a Mother Vertex in a Graph Java Solution.

Find a Mother Vertex in a Graph?

What is a Mother Vertex?

Ans: A mother vertex in a graph G = (V,E) is a vertex v such that all other vertices in G can be reached by a path from v.

So now there can be multiple cases such as:

Case 1:- Undirected Connected Graph : In this case, all the vertices are mother vertices as we can reach to all the other nodes in the graph.

Case 2:- Undirected/Directed Disconnected Graph : In this case, there is no mother vertices as we cannot reach to all the other nodes in the graph.

Case 3:- Directed Connected Graph : In this case, we have to find a vertex -v in the graph such that we can reach to all the other nodes in the graph through a directed path.

So for this we can simply do this approach just perform a DFS/BFS on all the vertices and find whether we can reach all the vertices from that vertex. This approach takes O(V(E+V)) time, which is very inefficient for large graphs.

We can fuirther decrease this complexity by using "Kosaraju’s Strongly Connected Component Algorithm" .Simply this algo says mother verices are always vertices of source component in component graph. If there exist mother vertex (or vertices), then one of the mother vertices is the last finished vertex in DFS. (Or a mother vertex has the maximum finish time in DFS traversal).
A vertex is said to be finished in DFS if a recursive call for its DFS is over, i.e., all descendants of the vertex have been visited.

So the Algorithm is:

Algorithm :

1)Do DFS traversal of the given graph. While doing traversal keep track of last finished vertex ‘v’. This step takes O(V+E) time.

2)If there exist mother vertex (or vetices), then v must be one (or one of them). Check if v is a mother vertex by doing DFS/BFS from v. This step also takes O(V+E) time.

Sample Code:

import java.io.*;
import java.util.*;

// This class represents a directed graph using adjacency list representation
class Graph
{
    private int V; // No. of vertices

    // Array of lists for Adjacency List Representation
    // an array of linked list
    // in this implementation the graph vertex values will be same array index
    private LinkedList<Integer> adj[];

    Graph(int v)
    {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i<v; ++i)
            adj[i] = new LinkedList();
    }

    //Function to add an edge into the graph
    void addEdge(int v, int w)
    {
        adj[v].add(w); // Add w to v's list.
    }

    // A function used by DFS
    void DFSUtil(int v,boolean visited[])
    {
        // Mark the current node as visited and print it
        visited[v] = true;

        // Recur for all the vertices adjacent to this vertex
        Iterator<Integer> i = adj[v].listIterator();
        while (i.hasNext())
        {
            int n = i.next();
            if (!visited[n])
                DFSUtil(n, visited);
        }
    }

    // The function to do DFS traversal. It uses recursive DFSUtil()
    void DFS()
    {
        // Mark all the vertices as not visited(set as false by default in java)
        boolean visited[] = new boolean[V];
        for (int i = 0; i < V; i++)
        {
            visited[i] = false;
        }  
     
        // The vertex that finishes last should be the mother node
        int v = -1;
        for (int i = 0; i < V; i++)
        {
            if (visited[i] == false)
            {
                DFSUtil(i, visited);
                v = i;
            }
        }
     
        // the node that finishes last in DFS can be the mother vertex
        for (int i = 0; i < V; i++)
        {
            visited[i] = false;
        }
     
        System.out.println(" Mother Vertex Detected At:"  + v);
     
        // we found the last finishing node
        // need to validate that
        // consider a individual node in the graph. It may not be the last vertex to finish.
        // to we need to confirm that
        DFSUtil(v, visited);
        for(int i = 0; i < V; i++)
        {
            if(visited[i] == false)
            {
                System.out.println("Not a mother vertex.Node that wasn't connected :" + i);      
                return;
            }
        }
        System.out.println(" Mother Vertex: "  + v);
    }

    public static void main(String args[])
    {
        Graph g = new Graph(7);
        // Graph g = new Graph(8);
     
        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 3);
        g.addEdge(4, 1);
        g.addEdge(6, 4);
        g.addEdge(6, 0);
        g.addEdge(5, 2);
        g.addEdge(5, 6);
        // g.addEdge(7, 7);

        // g.printGraph();
        g.DFS();
    }
 
 
    void printGraph()
    {
        for (int j= 0; j < V; ++j)
        {
            System.out.print("j:" + j + " :  ");
            Iterator<Integer> i = adj[j].listIterator();
            while (i.hasNext())
            {
                int n = i.next();
                System.out.print( " " + n + " ");
            }
            System.out.println(" ");
        }  
    }
}

Output: 

Mother Vertex Detected At:5
Mother Vertex: 5