Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Sample Examples 
2.
Naive approach 
2.1.
Implementation in C++
2.1.1.
Complexity Analysis
3.
Efficient approach 
3.1.
Steps of Algorithm 
3.2.
Implementation in C++
3.2.1.
Complexity Analysis
4.
Frequently Asked Questions
4.1.
What is the difference between directed and undirected graph? 
4.2.
What is the maximum number of edges in the undirected graph of Nodes N? 
4.3.
Which data structure is used for iterative BFS and DFS of the graph? 
4.4.
What is the difference between Breadth-first Search and Depth-first search? 
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Print All Mother Vertices In The Graph

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

Introduction

The problem states that we are given a graph G, and there are E edges and V vertices. Mother Vertex is defined as that vertex v, from which all other vertices of the graph are reachable.  There can be zero, one, or many mother vertex in the given graph, we need to find all the mother vertices. 

Let’s Discuss the sample example to understand the problem better. 

Sample Examples 

Example 1:

Input: Given graph

Output: 0 10 40 

Explanation: You can check from the given graph, that all nodes are reachable from nodes 0, 10, and 40. 

 

Example 2:

Input: Given graph 

Output: 1 2 3 4 5 

Explanation: You can reach any node, from any node, so all are mother vertices. 

Naive approach 

The idea is simple, for every node, either use BFS and DFS Algorithm to check whether all other nodes are reachable from a given node or not. 

Implementation in C++

// recursive function to find the sum of depths of all subtree
#include<bits/stdc++.h>
using namespace std;
// calling the dfs function for every node
void dfs(int sv, vector<vector<int>>&adj, vector<bool>&vis){
    vis[sv] = true;
    for(auto it : adj[sv]){
        if(!vis[it]) dfs(it, adj, vis);
    }
    return;
}

// checking if all the nodes are visited are not
bool allVisited(vector<bool>&vis){
    for(int i=0;i<vis.size();i++){
        if(!vis[i]) return false;
    }
    return true;
}

int main(){
    int v = 5;
    vector<vector<int>>adj(v);

    // graph given in sample case 2
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[4].push_back(0);

    // array to store the mother vertices
    vector<int>motherV;
    for(int i=0;i<v;i++){
        // intiliaze the visited vector
        // to keep check if the node is visited or not
        vector<bool>vis(v, false);
        
        // calling the dfs function
        dfs(i, adj, vis);
        
        // checking if all the nodes are visited or not
        if(allVisited(vis)) motherV.push_back(i);
    }
    
    // finally printing the number of mother vertices
    cout << "Total Number of mother vertices are : " << motherV.size() << endl;
    
    // printing the mother vertices
    for(auto it : motherV) cout << it << " ";
    cout << endl;
}

 

Output: 

Total Number of mother vertices are: 5
0 1 2 3 4

 

Complexity Analysis

Time Complexity: O(V(V*E))

Explanation: You need to traverse the complete graph for every vertex V. 

Space Complexity: O(V)

Explanation: Recursive stack space will be equal to a number of vertices V. 

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

Efficient approach 

The efficient approach is based on the Idea of kosaraju's algorithm and strongly connected component. We will first find any mother vertex in the graph by optimizing the naive approach. 

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

If a mother vertex (or vertices) exists, one of the mother vertices is the final vertex in DFS. (Or, in DFS traversal, a mother vertex has the fastest finish time.)

A recursive call for a vertex's DFS is considered to be ended in DFS if all descendants of the vertex have been visited.

Why this Idea works? 

Let v be the last completed vertex. Essentially, we must show that an edge from another vertex u to v cannot exist if u is not another mother vertex (or that a non-mother vertex u cannot exist such that u-v is an edge). There are two possible outcomes.

  • Before v, a recursive DFS call is done for u. Because v is reachable through u and a vertex finishes after all its children, if an edge u-v exists, v must have ended before u.
  • Before u, a recursive DFS call is done for v. If an edge u-v exists in this instance as well, either v must complete before u (contrary to our assumption that v is finished at the end) OR u must be reachable from v. (which means u is another mother vertex).

 

If the mother vertex exists, then the vertices of the strongly linked component that contains the mother vertex are all mother vertices because if v is a mother vertex and there is a path from u->v, then u must be a mother vertex as well.

Steps of Algorithm 

  • Traverse the given graph using DFS. Keep track of the last completed vertex 'v' while traversing. This step takes O(V+E) seconds to complete.
  • If a mother vertex (or vertices) exists, then v must be one of them (or one of them). DFS/BFS from v to see if it's a mother vertex. This phase requires O(V+E) time as well.
  • Find the transpose of the graph, and store it in the new adjacency list to find the strongly connected components.
  • Now call the DFS function on the mother vertex, and all other visited vertex through the mother vertex is also the mother vertices of the given graph because it is a strongly connected component with the mother vertex. 

Implementation in C++

// recursive function to find the sum of depths of all subtree
#include<bits/stdc++.h>
using namespace std;

// calling the dfs function for every node
void dfs(int sv, vector<vector<int>>&adj, vector<bool>&vis){
    vis[sv] = true;
    for(auto it : adj[sv]){
        if(!vis[it]) dfs(it, adj, vis);
    }
    return;
}

// checking if all the nodes are visited are not
void initializeVisited(vector<bool>&vis){
    for(int i=0;i<vis.size();i++){
        vis[i] = false;
    }
    return;
}

// function to get the transpose of the graph
void transposeGraph(vector<vector<int>>&adj, vector<vector<int>>&transpose){
    for(int i=0;i<adj.size();i++){
        for(auto it:adj[i]){
            transpose[it].push_back(i);
        }
    }
    return;
}

bool isMotherVertex(vector<vector<int>>&adj, int node){
    int n = adj.size();
    vector<bool>vis(n, false);
    dfs(node, adj, vis);
    for(int i=0;i<n;i++){
        if(!vis[i]) return false;
    }
    return true;
}

// function to get the all mother vertices of the graph
vector<int> allMotherVertices(vector<vector<int>>&adj){
    int n = adj.size();
    vector<bool>vis(n);
    
    // now we will try to find if there exist any mother vertex or not
    // using the algorithm discussed above
    int lastDfsCall = -1;
    initializeVisited(vis);
    for(int i=0;i<n;i++){
        if(!vis[i]){
            dfs(i, adj, vis);
            lastDfsCall = i;
        }
    }
    
    // now lastDfsCall may be the potential candidate for the
    // mother vertex, so we will check whether this element is
    // mother vertex or not, by running dfs on this, and check
    // if all elements can be visited using this element
    if(!isMotherVertex(adj, lastDfsCall)){
        vector<int>v;
        return v;
    }

    // now after checking the lastDfsCall is mother vertex, we
    // will find all the SCC of this lastDfsCall
    vector<vector<int>>transposeG(n);
    
    // finding the transpose of the graph
    transposeGraph(adj, transposeG);
    
    // again making the vis vector
    // false to keep the check on the visited array
    initializeVisited(vis);
   
    // dfs function
    dfs(lastDfsCall, transposeG, vis);

    // ans vector to store the final answer
    vector<int>ans;
    for(int i=0;i<n;i++){
        if(vis[i]==true){
            ans.push_back(i);
        }
    }
    // return the ans vector
    return ans;
}

int main(){
    int v = 5;
    vector<vector<int>>adj(v);

    // graph given in sample case 2
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(4);
    adj[4].push_back(0);

    // motherV to store the all mother vertices
    vector<int>motherV = allMotherVertices(adj);    
    cout << "Total Number of mother vertices are : " << motherV.size() << endl;
    
    // printing the mother vertices
    for(auto it : motherV) cout << it << " ";
    cout << endl;
}

 

Output: 

Total Number of mother vertices are: 5
0 1 2 3 4

 

Complexity Analysis

Time Complexity: O( |V| + |E |)

V is the number of vertices, and E is the number of edges since we are traversing only vertices and edges. Therefore the time complexity is O(|V| + |E|).   

Space Complexity: O( |V| + |E |)

In the worst case, O(|V| + |E|) recursive stack space and O(V) space for the visited array.  

Frequently Asked Questions

What is the difference between directed and undirected graph? 

The directed graph contains ordered pairs of vertices while the undirected contains unordered pairs of vertices. In a directed graph, edges represent the direction of vertices, while edges do not represent the direction of vertices. 

What is the maximum number of edges in the undirected graph of Nodes N? 

Ans: Each node can have an edge over every other n-1 node in an undirected graph. Therefore the total number of edges possible is n*(n-1)/2.

Which data structure is used for iterative BFS and DFS of the graph? 

Ans: In BFS, a queue data structure is used, while in DFS stack is used. 

What is the difference between Breadth-first Search and Depth-first search? 

The BFS uses queue data structure while DFS uses the stack data structure. BFS is more suitable for searching vertices closer to the given source, while DFS is more suitable for solutions away from the source.

Conclusion

In this article, we discussed the problem of finding all mothers of the graph, we have discussed the naive as well as an efficient approach for finding the mother vertices. We hope you understand the problem and solution properly. Now you can do more similar questions. 

Check out this problem - Duplicate Subtree In Binary Tree

Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, System Design, JavaScript, etc. Enroll in our courses, refer to the mock test and problems available, interview puzzles, and look at the interview bundle and interview experiences for placement preparations.

Thank you for reading. 

Until then, Keep Learning and Keep Coding.

Previous article
Pendant Vertices, Non-Pendant vertices, Pendant Edges, and Non-Pendant Edges of the Graph.
Next article
Dynamic Connectivity Problem
Live masterclass