Skip to main content

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:

Number of sink nodes in a 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
Last updated on by Kalkicode




Comment

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