Number of sink nodes in a graph
In graph theory, a sink node (also known as a terminal node or a leaf node) is a node in a directed graph that has no outgoing edges. In other words, it is a node that does not have any successors. The number of sink nodes in a graph refers to the count of such nodes present in the graph. For example, in the following graph:

Nodes 0, 2 and 4 are sink nodes as they don't have any outgoing edges. Therefore, the number of sink nodes in this graph is 3.
Program solution
//C Program
//Count Number of sink nodes 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;
};
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");
}
}
void connectEdge(struct Graph*node, int V ,int E)
{
// create Adjacency node
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
{
//Add node at last
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}else
{
printf("\n Memory overflow");
}
}
//Add Edge from Two given Nodes
void addEdge(struct Graph*node, int V ,int E)
{
if(V<size && E <size)
{
connectEdge(node,V,E);
}else
{
//not valid Vertices
printf("Invalid Node Vertices %d %d", V,E);
}
}
//Display Adjacency list of vertex
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");
}
}
//Count number of sink nodes
void sink_nodes(struct Graph*node)
{
if(node!=NULL)
{
int count=0;
for(int index=0;index<size;index++)
{
if(node[index].next==NULL)
{
count++;
}
}
printf("\n Sink nodes : %d\n",count );
}else
{
printf("Empty Graph");
}
}
int main()
{
size=5;
struct Graph*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
addEdge(node,1,0);
addEdge(node,1,2);
addEdge(node,3,0);
addEdge(node,3,2);
addEdge(node,3,4);
printGraph(node);
sink_nodes(node);
}
return 0;
}
Output
Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 :
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 :
Sink nodes : 3
//C++ program
//Count Number of sink nodes 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;
int size;//number of
public:
Graph(int);
void setData();
void addEdge(int,int);
void printGraph();
void sink_nodes();
void connect(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 ::connect(int V ,int E)
{
//add edge form V to E
//V and E is Node location
//first create Adjacency node
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
{
//Add node at last
while(temp->next!=NULL)
{
temp=temp->next;
}
temp->next=newEdge;
}
}
}
void Graph ::addEdge(int V ,int E)
{
//add edge form V to E
//V and E is Node location
if(V<size && E <size)
{
connect(V,E);
}else
{
//not valid Vertices
cout<<"Invalid Node Vertices "<< V<<" "<<E;
}
}
//Display Adjacency list of vertex
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;
}
}
//Count number of sink nodes
void Graph:: sink_nodes()
{
if(node!=NULL)
{
int count=0;
for(int index=0;index<size;index++)
{
if(node[index].next==NULL)
{
count++;
}
}
cout<<"\n Sink nodes : "<<count<<endl ;
}else
{
cout<<"\nEmpty Graph"<<endl;
}
}
int main()
{
//Create Object
Graph g=Graph(5);
//First set node keys
g.setData();
g.addEdge(1,0);
g.addEdge(1,2);
g.addEdge(3,0);
g.addEdge(3,2);
g.addEdge(3,4);
g.printGraph();
g.sink_nodes();
return 0;
}
Output
Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 :
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 :
Sink nodes : 3
//Java program
//Count Number of sink nodes 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;
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.nullPointerException
node[index]=new Vertices();
node[index].data=index;//set your data
node[index].next=null;
}
}
}
//connect two nodes
public void connect(int start,int end)
{
AjlistNode newEdge=new AjlistNode();
newEdge.id=end;//end node
newEdge.next=null;
if(node[start].next==null)
{
node[start].next=newEdge;
}else
{
AjlistNode temp=node[start].next;
while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newEdge;
}
}
//Add edge at the end
public void addEdge(int start,int end)
{
if(start < size && end < size && node != null)
{
connect(start,end);
}else{
System.out.println("\nInvalid nodes "+start+" "+end);
}
}
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;
}
}
}
}
//Count number of sink nodes
void sinkNodes()
{
if(node!=null)
{
int count=0;
for(int index=0;index<size;index++)
{
if(node[index].next==null)
{
count++;
}
}
System.out.printf("\n Sink nodes : %d\n",count );
}else
{
System.out.print("Empty Graph");
}
}
public static void main(String[] args)
{
int totalNode=5;
MyGraph g=new MyGraph(totalNode);
g.setData();
//Connected two node with Edges
g.addEdge(1,0);
g.addEdge(1,2);
g.addEdge(3,0);
g.addEdge(3,2);
g.addEdge(3,4);
g.printGraph();
g.sinkNodes();
}
}
Output
Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 :
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 :
Sink nodes : 3
#Python program
#Count Number of sink nodes in a graph
class AjLinkeNode:
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
#connect two node with edge
def connect(self,start,end):
new_edge=AjLinkeNode(end)
if(self.node[start].next==None):
self.node[start].next=new_edge
else:
temp=self.node[start].next
while(temp.next!=None):
temp=temp.next
temp.next=new_edge
#add edge
def addEdge(self,start,end):
#start,end is two nodes
if(self.size>start and self.size>start):
self.connect(start,end)
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 {0} :".format(index),end=" ")
temp=self.node[index].next
while temp!=None:
print(" {0}".format(temp.id),end=" ")
temp=temp.next
index+=1
#Detect cycle using DFS
def detectCycle(self, point, visit):
if(visit[point] >= 1):
visit[point]=visit[point]+1
return
visit[point]=1
temp=self.node[point].next
counter=0
while(temp!=None):
counter+=1
self.detectCycle(temp.id,visit)
temp=temp.next
if(counter>0):
visit[point] = visit[point]-counter
if(visit[point]<0):
visit[point]=-visit[point]
#Count number of sink nodes
def sinkNodes(self):
if(self.node!=None):
count=0;
index=0
while(index<self.size) :
if(self.node[index].next==None) :
count+=1;
index+=1
print("\n Sink nodes : ",count );
else :
print("Empty Graph");
def main():
g=Graph(5)
g.setData()
#Connected two node with Edges
g.addEdge(1,0);
g.addEdge(1,2);
g.addEdge(3,0);
g.addEdge(3,2);
g.addEdge(3,4);
g.printGraph();
g.sinkNodes();
if __name__=="__main__":
main()
Output
Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 :
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 :
Sink nodes : 3
//C# Graph
//Count Number of sink nodes in a graph
using System;
class AjlistNode
{
public int key;
public AjlistNode next;
public AjlistNode(int key)
{
this.key=key;
this.next=null;
}
}
class Node
{
public int data;
public AjlistNode next;
public Node(int data)
{
this.data=data;
this.next=null;
}
}
class MyGraph
{
//empty array
public Node[]node= new Node[] {};
public int size;
public MyGraph(int size)
{
this.size=size;
node=new Node[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.nullPointerException
node[index]=new Node(index);
}
}
}
//connect two nodes
public void connect(int start,int end)
{
AjlistNode newEdge=new AjlistNode(end);
if(node[start].next==null)
{
node[start].next=newEdge;
}else
{
AjlistNode temp=node[start].next;
while(temp.next!=null)
{
temp=temp.next;
}
temp.next=newEdge;
}
}
//Add edge at the end
public void addEdge(int start,int end)
{
if(start < size && end < size && node != null)
{
connect(start,end);
}else{
Console.WriteLine("\nnot valid node [{0}-{1}]",start,end);
}
}
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(" "+node[temp.key].data);
temp=temp.next;
}
}
}
}
//Count number of sink nodes
public void sinkNodes()
{
if(node!=null)
{
int count=0;
for(int index=0;index<size;index++)
{
if(node[index].next==null)
{
count++;
}
}
Console.WriteLine("\n Sink nodes : {0}",count );
}else
{
Console.WriteLine("Empty Graph");
}
}
}
class Program
{
static void Main(string[] args)
{
//create object
MyGraph g=new MyGraph(5);
g.setData();
//Connected two node with Edges
g.addEdge(1,0);
g.addEdge(1,2);
g.addEdge(3,0);
g.addEdge(3,2);
g.addEdge(3,4);
g.printGraph();
g.sinkNodes();
}
}
Output
Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 :
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 :
Sink nodes : 3
<?php
/*
* PHP Program
* Count Number of sink nodes 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);
}
}
}
public function connect($start,$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 addEdge($start,$end)
{
if($this->size > $start && $this->size>$end)
{
$this->connect($start,$end);
}
else
{
echo "\n Invalid node";
}
}
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;
}
}
}
}
//Count number of sink nodes
public function sink_nodes()
{
if($this->node!=null)
{
$count=0;
for($index=0;$index<$this->size;$index++)
{
if($this->node[$index]->next==null)
{
$count++;
}
}
echo ("\n Sink nodes : $count\n" );
}else
{
echo ("Empty Graph");
}
}
}
function main()
{
//create object
$g=new MyGraph(5);
$g->setData();
//Connected two node with Edges
$g->addEdge(1,0);
$g->addEdge(1,2);
$g->addEdge(3,0);
$g->addEdge(3,2);
$g->addEdge(3,4);
$g->printGraph();
$g->sink_nodes();
}
main();
?>
Output
Adjacency list of vertex 0 :
Adjacency list of vertex 1 : 0 2
Adjacency list of vertex 2 :
Adjacency list of vertex 3 : 0 2 4
Adjacency list of vertex 4 :
Sink nodes : 3
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.
New Comment