# Find Mother Vertex in a Graph

Mother Vertex in a Graph is a sequence of path or create a path which are goes to all other nodes. Generally there is possible one graph contains zero or more than one Mother Vertex. See this example.

Here given code implementation process.

``````//C Program Find Mother Vertex in a Graph
#include<stdio.h>
#include<stdlib.h>

struct AjlistNode{
int vId;//Vertices id
struct AjlistNode*next;
};

struct Graph{
int data; //node key value
struct AjlistNode*next;
};
void setData(struct Graph *);
int size; //number of nodes

//set node key value
void setData(struct Graph*node){
if(node!=NULL && size>0){
int index=0;
for(index;index<size;index++){
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}
}else{
printf("Vertic Node is Empty");
}
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E){
//add edge form V to E
//V and E is Node location
if(V<size && E <size){
struct AjlistNode *newEdge=(struct AjlistNode*)malloc(sizeof(struct AjlistNode));
if(newEdge!=NULL){

newEdge->next=NULL;
newEdge->vId=E;

struct AjlistNode *temp=node[V].next;

if(temp==NULL){
node[V].next=newEdge;
}else{
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=newEdge;
}
}else{
printf("\n Memory overflow");
}
}else{
//not valid Vertices
printf("Invalid Node Vertices %d  %d", V,E);
}
}
void printGraph(struct Graph*node){
if(node!=NULL){
struct AjlistNode *temp=NULL;
for(int index=0;index<size;index++){
printf("\n Adjacency list of vertex %d  :",index);
temp=node[index].next;
while(temp!=NULL){
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

printf("  %d",node[temp->vId].data);
temp=temp->next;
}
}
}else{
printf("Empty Graph");
}
}

void check_vertex(int point,int *visit,struct Graph*node){

if(visit[point]==1){
return;
}else{
visit[point]=1;
struct AjlistNode *temp=node[point].next;
while(temp!=NULL){
check_vertex(temp->vId,visit,node);
temp=temp->next;
}
}
}
int main(){

size=7;
struct Graph*node=NULL;

int *visit=(int*)calloc(size,sizeof(int));

node=(struct Graph*)malloc(sizeof(struct Graph)*size);

if(node==NULL){
printf("\n Memory overflow");
}else{
//First set node keys
setData(node);

//Connected two node with Edges

printGraph(node);
printf(" \nMother Vertex :");

int test=0,status=1;

while(test<size){
status=1;
check_vertex(test,visit,node);

//When current node are visit other nodes
//Then that is a Mother Vertex
for(int index=0;index<size;index++){

if(visit[index]!=1)
{
status=0;
}
//reset element value
visit[index]=0;
}
if(status==1){
printf(" %d ",test);
}
test++;
}

}
return 0;
}``````

#### Output

`````` Adjacency list of vertex 0  :
Adjacency list of vertex 1  :  0  4
Adjacency list of vertex 2  :  5
Adjacency list of vertex 3  :  1  2  6
Adjacency list of vertex 4  :  3
Adjacency list of vertex 5  :  0
Adjacency list of vertex 6  :
Mother Vertex : 1  3  4 ``````
``````//C++ Program, Find Mother Vertex in a Graph
#include<iostream>
using namespace std;
struct AjlistNode
{
int vId;//Vertices id
struct AjlistNode*next;
};
struct Vertices
{
int data; //node key value
struct AjlistNode*next;
};

class Graph
{
Vertices *node;

public:
int size;//number of node
Graph(int);
void setData();
void printGraph();
void check_vertex(int,int *);
};

Graph::Graph(int size)
{
this->size=size;
//set number of nodes
node=new Vertices[size];
}
//set node key value
void Graph:: setData()
{
if(node!=NULL)
{
int index=0;
for(index;index<size;index++)
{
//set vertic node data
node[index].data=index;//set node key
//Initial no AjlistNode
//set NULL Value
node[index].next=NULL;
}
}else
{
cout<<"Vertic Node is Empty"<<endl;
}
}

//Add Edge from Two given Nodes
void Graph ::addEdge(int V ,int E)
{
//Add edge form V to E
//V and E is Node location
if(V<size && E <size)
{
AjlistNode *newEdge=new AjlistNode;
if(newEdge!=NULL)
{

newEdge->next=NULL;
newEdge->vId=E;

AjlistNode *temp=node[V].next;

if(temp==NULL)
{
node[V].next=newEdge;
}else
{
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}
}else
{
//not valid Vertices
cout<<"Invalid Node Vertices "<< V<<" "<<E;
}
}
void Graph::printGraph()
{
if(node!=NULL)
{
AjlistNode *temp=NULL;
for(int index=0;index<size;index++)
{
cout<<"\n Adjacency list of vertex "<<index<<" :";
temp=node[index].next;
while(temp!=NULL)
{
//temp->vId is graph node vertices
//in this case temp->vId is same as
//node[temp->vId].data

cout<<" "<<node[temp->vId].data;
temp=temp->next;
}
}
}else
{
cout<<"Empty Graph"<<endl;
}
}
//Check Path of given vertex
void Graph:: check_vertex(int point,int *visit){

if(visit[point]==1){
return;
}else{
visit[point]=1;
AjlistNode *temp=node[point].next;
while(temp!=NULL){
check_vertex(temp->vId,visit);
temp=temp->next;
}
}
}

int main()
{

int size = 7;
//Create Object
Graph g(size);
//First set node keys
g.setData();

//Connected two node with Edges

g.printGraph();

//Create array
int visit[size]={0};

cout<<" \n Mother Vertex :";
int test=0,status=1;

while(test<size)
{
status=1;
g.check_vertex(test,visit);

//When current node are visit other nodes
//Then that is a Mother Vertex
for(int index=0;index<size;index++)
{

if(visit[index]!=1)

{
status=0;
}
//reset element value
visit[index]=0;
}
if(status==1)
{
cout<<"  "<<test;
}
test++;
}
return 0;
}``````

#### Output

`````` Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 1 2 6
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 0
Adjacency list of vertex 6 :
Mother Vertex :  1  3  4``````
``````//Java Program, Find Mother Vertex in a Graph
public class MyGraph
{

static class AjlistNode
{
int id;//Vertices node key
AjlistNode next;
}
static class Vertices
{
int data;
AjlistNode next;
}

//number of Vertices
static int size;
public Vertices node[];
MyGraph(int size)
{
//set value
this.size=size;

node=new Vertices[size];

}

//set initial node value
public void setData(){
if(node==null )
{
System.out.println("\nEmpty Graph");
}else
{
for(int index=0;index<size;index++)
{
// avoid java.lang.null PointerException
node[index]=new Vertices();
node[index].next=null ;
}
}
}

if(S<size && E<size && node!=null )
{
AjlistNode newEdge=new AjlistNode();
newEdge.id=E;//end node
newEdge.next=null ;
if(node[S].next==null )
{
node[S].next=newEdge;
}else
{
AjlistNode temp=node[S].next;
while(temp.next!=null )
{
temp=temp.next;
}
temp.next=newEdge;
}

}else{
System.out.println("\nEmpty Graph");
}
}

public void printGraph()
{
if(size>0&&node!=null )
{
for(int index=0;index<size;index++)
{
System.out.print("\nAdjacency list of vertex "+index+" :");
AjlistNode temp=node[index].next;
while(temp!=null )
{
System.out.print(" "+node[temp.id].data);
temp=temp.next;
}
}
}
}
//Check Path of given vertex
public void  checkVertex(int point,int  []visit){

if(visit[point]==1){
return;
}else{
visit[point]=1;
AjlistNode  temp=node[point].next;
while(temp!=null ){
checkVertex(temp.id,visit);
temp=temp.next;
}
}
}

public static void main(String[] args) {
int totalNode=7;

MyGraph g=new MyGraph(totalNode);
g.setData();
//Connected two node with Edges

g.printGraph();

//Create array
int []visit=new int[totalNode];

System.out.print(" \n Mother Vertex :");
int test=0,status=1;

while(test<totalNode)
{
status=1;
g.checkVertex(test,visit);

//When current node are visit other nodes
//Then that is a Mother Vertex
for(int index=0;index<totalNode;index++)
{

if(visit[index]!=1)

{
status=0;
}
//reset element value
visit[index]=0;
}
if(status==1)
{
System.out.print("  "+test);
}
test++;
}

}
}``````

#### Output

``````Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 1 2 6
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 0
Adjacency list of vertex 6 :
Mother Vertex :  1  3  4``````
``````#Python , Find Mother Vertex in a Graph
def __init__(self,data):
self.id=data
self.next=None

class Vertices:
def __init__(self,data):
self.data=data
self.next=None

class Graph:
"""Constructor for Graph"""
def __init__(self, size):
self.size=size
self.node=[]

def setData(self):
if(self.size>0 and self.node!=None):
index=0
while(index<self.size):
self.node.append(Vertices(index))
index+=1

#S and E is two nodes
if(self.size>S and self.size>E):
if(self.node[S].next==None):
self.node[S].next=new_edge
else:
temp=self.node[S].next
while(temp.next!=None):
temp=temp.next
temp.next=new_edge
else:
print("Invalid nodes")

def printGraph(self):
if(self.size>0 and self.node!=None):
index=0
while(index<self.size):
print("\nAdjacency list of vertex ",index,end=" : ")
temp=self.node[index].next
while temp!=None:
print(temp.id,end=" ")
temp=temp.next
index+=1
def checkVertex(self,point,visit):

if(visit[point]==1):
return
else:
visit[point]=1
temp=self.node[point].next
while(temp!=None ):
self.checkVertex(temp.id,visit)
temp=temp.next

def main():
totalNode=7
g=Graph(totalNode)
g.setData()
#Connected two node with Edges
g.printGraph()
#Create list
visit=[0]*totalNode

print(" \n Mother Vertex :",end=" ")
test=0
status=1

while(test<totalNode):
status=1
g.checkVertex(test,visit)

#When current node are visit other nodes
#Then that is a Mother Vertex
index=0
while(index<totalNode):

if(visit[index]!=1):
status=0

#reset element value
visit[index]=0
index+=1
if(status==1):
print(test,end=" ")
test+=1

if __name__=="__main__":
main()``````

#### Output

``````Adjacency list of vertex  0 :
Adjacency list of vertex  1 : 0 4
Adjacency list of vertex  2 : 5
Adjacency list of vertex  3 : 1 2 6
Adjacency list of vertex  4 : 3
Adjacency list of vertex  5 : 0
Adjacency list of vertex  6 :
Mother Vertex : 1 3 4 ``````
``````//C# Program, Find Mother Vertex in a Graph

using System;
public class AjlistNode
{
public int id;//Vertices node key
public AjlistNode next;
}
public class Vertices
{
public int data;
public AjlistNode next;
}
public class MyGraph
{

//number of Vertices
public int size;

public Vertices[]node= new Vertices[] {};
MyGraph(int size)
{
//set value
this.size=size;

node=new Vertices[size];

}

//set initial node value
public void setData(){
if(node==null )
{
Console.WriteLine("\nEmpty Graph");
}else
{
for(int index=0;index<size;index++)
{
// avoid java.lang.null PointerException
node[index]=new Vertices();
node[index].next=null ;
}
}
}

if(S<size && E<size && node!=null )
{
AjlistNode newEdge=new AjlistNode();
newEdge.id=E;//end node
newEdge.next=null ;
if(node[S].next==null )
{
node[S].next=newEdge;
}else
{
AjlistNode temp=node[S].next;
while(temp.next!=null )
{
temp=temp.next;
}
temp.next=newEdge;
}

}else{
Console.WriteLine("\nEmpty Graph");
}
}

public void printGraph()
{
if(size>0&&node!=null )
{
for(int index=0;index<size;index++)
{
Console.Write("\nAdjacency list of vertex "+index+" :");
AjlistNode temp=node[index].next;
while(temp!=null )
{
Console.Write(" {0}",node[temp.id].data);
temp=temp.next;
}
}
}
}
//Check Path of given vertex
public void  checkVertex(int point,int  []visit){

if(visit[point]==1){
return;
}else{
visit[point]=1;
AjlistNode  temp=node[point].next;
while(temp!=null ){
checkVertex(temp.id,visit);
temp=temp.next;
}
}
}

static void Main(string[] args)
{
int totalNode=7;

MyGraph g=new MyGraph(totalNode);
g.setData();
//Connected two node with Edges

g.printGraph();

//Create array
int []visit=new int[totalNode];

Console.Write(" \n Mother Vertex :");
int test=0,status=1;

while(test<totalNode)
{
status=1;
g.checkVertex(test,visit);

//When current node are visit other nodes
//Then that is a Mother Vertex
for(int index=0;index<totalNode;index++)
{

if(visit[index]!=1)

{
status=0;
}
//reset element value
visit[index]=0;
}
if(status==1)
{
Console.Write("  "+test);
}
test++;
}

}
}``````

#### Output

``````Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 4
Adjacency list of vertex 2 : 5
Adjacency list of vertex 3 : 1 2 6
Adjacency list of vertex 4 : 3
Adjacency list of vertex 5 : 0
Adjacency list of vertex 6 :
Mother Vertex :  1  3  4
``````
``````<?php
/*
* PHP Program,Find Mother Vertex in a Graph

*/

class AjlistNode{
public \$key;
public \$next;
function __construct(\$key)
{
\$this->key=\$key;
\$this->next=NULL;
}
}
class Node{
public \$data;
public \$next;
function __construct(\$data)
{
\$this->data=\$data;
\$this->next=NULL;
}
}

class MyGraph{

public \$node;
public \$size;

function __construct(\$size){
\$this->size=\$size;
\$this->node=[];  //empty array

}
public function setData(){
if(\$this->size>0){
for(\$index=0;\$index<\$this->size;\$index++){
\$this->node[\$index]=new Node(\$index);
}

}
}
if(\$this->size > \$start && \$this->size>\$end){
\$newEdge=new AjlistNode(\$end);
if(\$this->node[\$start]->next==NULL){
\$this->node[\$start]->next=\$newEdge;
}else{

\$temp=\$this->node[\$start]->next;
while(\$temp->next!=NULL){
\$temp=\$temp->next;
}
\$temp->next= \$newEdge;
}
}
}
public function printGraph(){
if(\$this->size>0 && count(\$this->node)>0 && \$this->node!=NULL){
for(\$index=0;\$index<\$this->size;\$index++){
echo ("\nAdjacency list of vertex ".\$index." : ");
\$temp=\$this->node[\$index]->next;
while(\$temp!=NULL){
echo (" ".\$this->node[\$temp->key]->data);
\$temp=\$temp->next;
}
}
}
}
//Check Path of given vertex
public function checkVertex(\$point,& \$visit){

if(\$visit[\$point]==1){
return;
}else{
\$visit[\$point]=1;
\$temp=\$this->node[\$point]->next;
while(\$temp!=NULL ){
\$this->checkVertex(\$temp->key,\$visit);
\$temp=\$temp->next;
}
}
}

}

function main(){
\$totalNode=7;
//create object
\$g=new MyGraph(\$totalNode);
\$g->setData();

//Connected two node with Edges

\$g->printGraph();

//Create array
\$visit=array_fill(0, \$totalNode, 0);;

echo (" \n Mother Vertex :");
\$test=0;
\$status=1;

while(\$test<\$totalNode)
{
\$status=1;
\$g->checkVertex(\$test, \$visit);

//When current node are visit other nodes
//Then that is a Mother Vertex
for(\$index=0;\$index<\$totalNode;\$index++)
{

if(\$visit[\$index]!=1)

{
\$status=0;
}
//reset element value
\$visit[\$index]=0;
}
if(\$status==1)
{
echo("  ".\$test);
}
\$test++;
}

}
main();
?>``````

#### Output

``````Adjacency list of vertex 0 :
Adjacency list of vertex 1 :  0 4
Adjacency list of vertex 2 :  5
Adjacency list of vertex 3 :  1 2 6
Adjacency list of vertex 4 :  3
Adjacency list of vertex 5 :  0
Adjacency list of vertex 6 :
Mother Vertex :  1  3  4``````

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.