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

Number of sink nodes in a graph

Program solution

Output

Output

Output

Output

Output

Output

Comment

New Comment