Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction👨‍🏫
2.
Sink node
3.
Problem🤔
3.1.
Input
3.2.
Output
3.2.1.
Explanation
4.
Algorithm
4.1.
Dry run
4.2.
Implementation in C++
4.2.1.
Output
4.3.
Implementation in Java
4.3.1.
Output
4.4.
Implementation in Python
4.4.1.
Output
5.
Complexity Analysis
5.1.
Time Complexity
5.1.1.
Explanation
5.2.
Space complexity
5.2.1.
Explanation
6.
Frequently Asked Questions
6.1.
How do you count nodes in a graph?
6.2.
What is a sink vertex?
6.3.
What are the source and sink in a graph?
6.4.
How many edges does a graph have with N nodes?
6.5.
What is DFS?
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Calculate the number of sink nodes in a graph

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

Introduction👨‍🏫

Number of sink nodes in a graph

 

A graph is a non-linear Data Structure made up of nodes, also known as vertices and edges. These nodes may be found in either directed or undirected structures.

Their edges in a directed graph can be incoming or outgoing from a given node. In a directed graph, a node with no outgoing edges is known as a sink. A sink is simply someone who receives a lot but never chooses to give back.

Before moving on to the discussion of this problem, you need to understand the concept of the Sink node.  

Sink node

A node where the outdegree is 0 and has a positive value for indegree is called the sink node. That is, there are only incoming arcs to the node and no outgoing arcs to the node.

In degree

Out degree

The number of arcs exiting from the node is called the outdegree of that node.  The number of arcs entering the node is called the in-degree of that node.

 

in-degree and out-degree graph

 

Nodes

In degree

Out degree

A

0

2

B

1

2

C

1

1

D

3

0

 

In the above graph, node 'D' is the Sink node as its outdegree is 0.

I hope from the above example, and you now understand the concept of sink node.

Now, let us learn how to calculate the number of sink nodes in a graph. 

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

Problem🤔

In the given graph of n nodes (numbered from 1 to n) and m edges, we need to calculate the number of sink nodes in a graph.

 

Input

Number of sink nodes in a graph

Output

Sink nodes = 3

Explanation

In the above fig, the dotted nodes (0, 2, 4) represent sink nodes, whereas node 1 and node 3 represent source nodes. Now let us see the code implementation to calculate the number of sink nodes in a graph.

Algorithm

  • First, we will define the Number of Vertices and set the value.
  • Then, we will set the initial node value and connect two nodes. 
  • Add the edge from two given Nodes.
  • Add edge form V to E. Here, V and E are node locations,
  • Create Adjacency node.
  • Finally, we will count the number of sink nodes.

Dry run

dry run

The implementation of the above algorithm is given below.

Implementation in C++

//C++ program to calculate the number of sink nodes in a graph
#include<iostream>

using namespace std;

struct AjaclistNode {
  //Vertices id
  int verId;
  struct AjaclistNode * next;
};

struct Vertices {
  //node key value
  int data;
  struct AjaclistNode * next;
};

class Graph {
  Vertices * node;

  int size;
  public:
    Graph(int);
  void SetData();
  void AddEdge(int, int);
  void PrintGraph();
  void SinkNodes();
  void Connect(int, int);
};
Graph::Graph(int size) {
  this -> size = size;
  //set the number of nodes
  node = new Vertices[size];
}
//set the node key value
void Graph::SetData() {
  if (node != NULL) {
    int index = 0;

    for (index; index < size; index++) {
      //set the vertic node data
      node[index].data = index;
      //set the node key
      //Initial no AjlistNode set NULL Value
      node[index].next = NULL;
    }
  } else {
    cout << "Vertic Node is Empty" << endl;
  }
}
//Add the edge from two given Nodes
void Graph::Connect(int V, int E) {
  /*add edge form V to E. Here, V and E are Node location
  first, create Adjacency node*/
  AjaclistNode * NewEdge = new AjaclistNode;

  if (NewEdge != NULL) {

    NewEdge -> next = NULL;
    NewEdge -> verId = E;

    AjaclistNode * 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. Here, V and E are Node location
  if (V < size && E < size) {
    Connect(V, E);

  } else {
    //not valid Vertices
    cout << "Invalid Node Vertices " << V << " " << E;
  }
}

//Display the adjacency list of vertex
void Graph::PrintGraph() {
  if (node != NULL) {
    AjaclistNode * temp = NULL;
    for (int index = 0; index < size; index++) {
      cout << "\n Adjacency list of vertex " << index << " :";
      temp = node[index].next;
      while (temp != NULL) {
        /*temp->verId is graph node vertices in this case temp->verId 
        is same as node[temp->verId].data*/

        cout << " " << node[temp -> verId].data;
        temp = temp -> next;
      }
    }
  } else {
    cout << "Empty Graph" << endl;
  }
}
//Count the Number of  sink nodes
void Graph::SinkNodes() {
  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 the 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.SinkNodes();

  return 0;
}

Output

output

Implementation in Java

//Java program to calculate the number of sink nodes in a graph
import java.util.*;

public class Main {

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

  //the Number of Vertices
  static int size;
  Vertices node[];

  Main(int size) {
    //set the value
    this.size = size;
    node = new Vertices[size];

  }

  //set theinitial node value
  public void SetData() {
    if (node == null) {
      System.out.println("\n Empty Graph");
    } else {
      for (int index = 0; index < size; index++) {
        // avoid the java.lang.nullPointerException
        node[index] = new Vertices();
        node[index].data = index; //set your data
        node[index].next = null;
      }
    }
  }
  //connect the two nodes
  public void Connect(int Start, int End) {
    AjaclistNode NewEdge = new AjaclistNode();
    //End node
    NewEdge.id = End;
    NewEdge.next = null;
    if (node[Start].next == null) {
      node[Start].next = NewEdge;
    } else {
      AjaclistNode 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("\n Invalid nodes " + Start + " " + End);
    }
  }

  public void PrintGraph() {

    if (size > 0 && node != null) {
      for (int index = 0; index < size; index++) {
        System.out.print("\n Adjacency list of vertex " + index + ": ");

        AjaclistNode temp = node[index].next;

        while (temp != null) {
          System.out.print(" " + node[temp.id].data);

          temp = temp.next;
        }
      }
    }
  }

  //Count the 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;

    Main g = new Main(TotalNode);
    g.SetData();
    //Connected 2 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

output

Implementation in Python

#Python program to count the number of sink nodes in a graph

class AjacLinkeNode:
  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 the two node with  edge
  def Connect(Self,Start,End):
    NewEdge=AjacLinkeNode(End)
    if(Self.node[Start].next==None):
      Self.node[Start].next=NewEdge
    else:
      temp=Self.node[Start].next
      while(temp.next!=None):
        temp=temp.next
      temp.next=NewEdge  

  #add the edge
  def AddEdge(Self,Start,End):

    #Start, End in 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("\n Adjacency 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 the cycle using DFS(Depth-first search)
  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 the 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 nodes with the Edges

  g.AddEdge(0,1);
  g.AddEdge(0,4);
  g.AddEdge(3,1);
  g.AddEdge(3,4);
  g.AddEdge(3,2);
  g.PrintGraph();
  g.SinkNodes();

if __name__=="__main__":
    main()

Output

output in python

Complexity Analysis

Time Complexity

Time complexity is O(m + n). Here m is the number of nodes, and n is the number of edges.

Explanation

In adjacency, the list node keeps track of all of its neighboring edges. Let's say that there are m nodes and n edges in the graph.

We can find all the neighbors of a node just by traversing its adjacency list only once, that too in linear time.

The sum of sizes of the adjacency lists of all nodes in a directed graph is n. Thus, for a directed graph, the time complexity is O(m) + O(n) = O(m + n).

Space complexity

Space complexity for this algorithm is O(m). Here m is the number of nodes, and n is the number of edges.

Explanation

Because we're using a queue (FIFO architecture) to keep track of the visited nodes, the queue would take the size of the graph's nodes (or vertices). Hence, the space complexity is O(m).

Now it’s time for some frequently asked questions.

FAQs

 

Frequently Asked Questions

How do you count nodes in a graph?

Using a depth-first search, we have to count the number of non-reachable nodes from the given head node. In the graph, if we consider 0 as a head node, then the node 0, 1, and 2 are reachable. We mark all the reachable nodes as visited.

What is a sink vertex?

A sink vertex is a vertex of a directed graph with no outgoing edges. Simply, a vertex with out-degree 0.

What are the source and sink in a graph?

The degree of a node is the sum of its in-degree and outdegree. A node is considered a source in a graph if it has an in-degree of 0 (no nodes have a source as their destination); likewise, a node is considered a sink in a graph if it has an outdegree of 0 (no nodes have a sink as their source).

How many edges does a graph have with N nodes?

If a graph has N nodes, then there are N - 1 directed edges that can lead from it (going to every other node). Hence, the maximum number of edges is N * (N - 1).

What is DFS?

In the depth First Search (DFS) algorithm we traverses a graph in a depthward motion and use a stack to remember and get the next vertex to start a search when a dead end occurs in any iteration.

Conclusion

In the above article, we have learned to calculate the number of sink nodes in a graph with the help of an advanced topic related to graphs, "sink nodes." We have discussed the approach using java, python, and CPP languages.

Check out this problem - Connect Nodes At Same Level

Find more such exciting algorithms in our library section, and solve interesting questions on our practice platform Coding Ninjas Studio. Keep Learning.

Happy Coding!

Previous article
Find all Reachable Nodes from Every Node Present in a Given Set
Next article
Maximize the shortest path between given vertices by adding a single edge
Live masterclass