Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
How to locate the mother vertex?
3.
Example
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Brute Force Approach
5.
How we can improve?
5.1.
Implementation
6.
Algorithm
6.1.
C++ Code
6.2.
Java Code
6.3.
Output
7.
Complexities
7.1.
Time complexity 
7.2.
Space complexity 
8.
Frequently Asked Questions
8.1.
What does a graph's mother vertex mean?
8.2.
What do you mean by depth of a vertex?
8.3.
What is the load factor of a hash table?
8.4.
Why does DFS employ stack?
8.5.
How is a vertex set written?
9.
Conclusion
Last Updated: Mar 27, 2024
Medium

Mother vertex in a Graph

Author Manan Singhal
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

A graph is a type of non-linear data structure. A graph is defined as a group of vertices, and edges are used to connect these vertices. There are many different types of graphs, such as directed, undirected, weighted, unweighted, cyclic, acyclic, etc. There are many real-life applications of the graph. They are used in maps, social media, path optimization algorithms, etc.

In the article, we will discuss one of the popular questions, finding the mother vertex in a graph.

Problem Statement

A vertex v that can be accessed via a path from all other vertices in a graph G = (V, E) is known as a mother vertex. A graph may contain several mother vertices. Any of these must be output.

How to locate the mother vertex?

  • Undirected Connected Graph: All of the vertices in this case are mother vertices since we can connect to every other node in the graph through them.
     
  • Undirected/Directed Disconnected Graph: There are no mother vertices in this situation since we are unable to access all of the other nodes in the graph.
     
  • Directed Connected Network: In this scenario, we must locate a vertex (v) in the graph that allows us to take a directed path to all other nodes in the graph.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Example

Input

Input image

Output

0, 1, 2

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.

Depth first search

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.

Implementation

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;
}

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));
    }
}

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:

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!

Previous article
Difference Between Graph And Tree
Next article
Pendant Vertices, Non-Pendant vertices, Pendant Edges, and Non-Pendant Edges of the Graph.
Live masterclass