Mother vertex in a Graph

Example

Input

Output

0, 1, 2

You can also try this code with Online Java Compiler

Run Code

Explanation

1. For mother vertex: 0
   To reach 1: 0 - 2 - 1
   To reach 2: 0 - 2
   To reach 3: 0 - 3
   To reach 4: 0 - 3 - 4
    
2. For mother vertex: 1
   To reach 0: 1 - 0
   To reach 2: 1 - 0 - 2
   To reach 3: 1 - 0 - 3
   To reach 4: 1 - 0 - 3 - 4
    
3. For mother vertex: 2
   To reach 0: 2 - 1 - 0
   To reach 1: 2 - 1
   To reach 3: 2 - 1 - 0 - 3
   To reach 4: 2 - 1 - 0 - 3 - 4

Brute Force Approach

A simple method would be to do a DFS/BFS on each vertex to determine if we could reach all the other vertices from that vertex. This method is particularly inefficient for big graphs because it requires O(V(E+V)) time.

How we can improve?

Mother vertices are always the vertices of the source component in the component graph in a graph of strongly connected components. The concept is supported by the following fact.

If the mother vertex exists, then the last finished vertex in DFS is one of the mother vertexes.

If a recursive call for a vertex's DFS is complete, meaning all of the vertex's descendants have been visited, the vertex is said to be finished in DFS.

Implementation

Let v be the final finished vertex. In essence, we must demonstrate that if u is not a different mother vertex, there cannot be an edge from u to v. There are two potential outcomes.

Before v, a recursive DFS call is done for u. Because v can be reached from u and a vertex finishes after all of its offspring, if an edge u-v exists, v must have finished before u.

Before u, a recursive DFS call is done for v. If an edge u-v exists in this situation as well, then either v must complete before u or u must be reachable from v.

Algorithm

1. DFS traverses the provided graph. Keep track of the final vertex ('V') while traversing. This process requires O(V+E) time.
    
2. If a mother vertex (or vertex(s)) exists, then v must be one (or one of them). DFS/BFS from v should be used to determine if v is a mother vertex. The time complexity of this phase is O(V+E).
    

Let’s start with the implementation of the code.

C++ Code

/* C++ program: Mother vertex in a Graph */
#include <bits/stdc++.h>

using namespace std;

/* This function will perform DFS. */
void dfs(int s, vector<bool> &vis, vector<int> adj[])
{
	vis[s] = true;
	for (auto it = adj[s].begin(); it != adj[s].end(); ++it)
		if (vis[*it] == false)
			dfs(*it, vis, adj);
}


/* function returns a mother vertex else returns -1 */
int findMother(vector<int> adj[], int V)
{
	vector<bool> vis(V, false);
	int v;
	
	for (int i = 0; i < V; i++)
	{
		if (vis[i] == false)
		{
			/* Performing DFS from every unvisited node. */
			dfs(i, vis, adj);
			v = i;
		}
	}
	fill(vis.begin(), vis.end(), false);
	dfs(v, vis, adj);
	/* If any vertex is not visited then return -1, No mother vertex found. */
	for (int i = 0; i < V; i++)
		if (vis[i] == false)
			return -1;
	return v;
}

int main()
{
	int V = 5;
	vector<int> adj[V];
	
	adj[0].push_back(2);
	adj[0].push_back(3);
	adj[1].push_back(0);
	adj[2].push_back(1);
	adj[3].push_back(4);
	
	cout << "Mother vertex in a graph: " << findMother(adj, V);

	return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Java Code

/* Java program: Mother vertex in a Graph */
import java.util.*;

class Main{
    
    /* function to print DFS starting from v */
    static void printDfsFromParticularVertex(ArrayList<ArrayList<Integer>> g, int v, boolean[] visited) {
        
    	visited[v] = true;
    	
    	/* Recursion for all the vertices adjacent to the following vertex */
    	for(int x : g.get(v)) {
    		if (!visited[x]) {
    			printDfsFromParticularVertex(g, x, visited);
    		}
    	}
    }
    
    static void addEdgeToGraph(int u, int v, ArrayList<ArrayList<Integer>> a) {
        /* adding edge to create a graph */
    	a.get(u).add(v);
    }
    
    /* function returns a mother vertex else returns -1 */
    static int findMotherVertex(ArrayList<ArrayList<Integer>>g, int V) {
    	
    	/* DFS: visited list */
    	boolean[] visited = new boolean[V];
    	
    	/* To save the final vertex */
    	int v = -1;
    	
    	for(int i = 0; i < V; i++) {
    		if (!visited[i]) {
    			printDfsFromParticularVertex(g, i, visited);
    			v = i;
    		}
    	}
    	
    	boolean[] check = new boolean[V];
    	printDfsFromParticularVertex(g, v, check);
    	for(boolean val : check) {
    		if (!val) {
    			return -1;
    		}
    	}
    	return v;
    }
    
    /* Main program */
    public static void main(String[] args) {
        
        /* number of vertices */
    	int V = 5;
    	
    	int E = 5;
    	
    	ArrayList<ArrayList<Integer>> a = new ArrayList<ArrayList<Integer>>();
    	
    	for(int i = 0; i < V; i++) {
    		a.add(new ArrayList<Integer>());
    	}
    	
    	addEdgeToGraph(0, 2, a);
    	addEdgeToGraph(0, 3, a);
    	addEdgeToGraph(1, 0, a);
    	addEdgeToGraph(2, 1, a);
    	addEdgeToGraph(3, 4, a);
    	
    	System.out.println("Mother vertex in a graph: " + findMotherVertex(a, V));
    }
}

You can also try this code with Online Java Compiler

Run Code

Output

0

Complexities

Time complexity 

O(V+E), where V is the vertex in a graph and E represents edges in the graph.

Reason: The given graph has been traversed using DFS Algorithm, and we maintain track of the last completed vertex, "v," which takes O(V+E) time.

We start a DFS from "v" once more, and this time it takes O(V+E) time to determine whether "v" is the mother vertex or not.

As a result, O(V+E) is the total time complexity.

Space complexity 

O(V), where V is the vertex in a graph

Reason: The complexity of space is of order N because auxiliary space is utilized when building arrays.
Check out this problem - No of Spanning Trees in a Graph

Frequently Asked Questions

What does a graph's mother vertex mean?

A mother vertex in a graph is a vertex from which a directed path can reach every node in the graph. In other words, a mother vertex is a vertex v such that a path from v may reach every other vertex in a graph G = (V, E).

What do you mean by depth of a vertex?

The number of branches that lead from a root to a vertex determines the vertex's depth. Therefore, the root's depth is zero. The number of the vertex in the path from the root to the vertex determines the vertex's level.

What is the load factor of a hash table?

The load factor can be defined as (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased, and n is the overall size of the hash table.

Why does DFS employ stack?

When a dead end occurs during any iteration, the Depth First Search (DFS) method employs a stack to keep track of where to find the next vertex to begin a search.

How is a vertex set written?

The letters V (G) and E stand for the vertex set and edge set, respectively, of graph G. If the context makes the specific graph, we may simply refer to these sets as V and E.

Conclusion

In the article, we have discussed one popular question: finding the mother vertex in a graph. We hope that this article will help you understand the concept of a graph, and if you want to learn more about the graph, check out our other blogs on graphs:

• Introduction to Graphs
• Graph Theory
• Graph Representation
• Application if graph data structure
• Properties of Graph
• Graph Types and Applications
• Implementation of Graph in Java
• Implementation of Graph in Python
• Construct a Graph from the size of components of each node
• Detect cycle in directed graph
• Detect cycle in an undirected graph
   

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!