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.
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đź‘¨â€ŤđźŹ«

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 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.

### 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,
• Finally, we will count the number of sink nodes.

### 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 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
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 {
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.PrintGraph();
g.SinkNodes();

return 0;
}``````

### 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;
}
}
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.PrintGraph();
g.SinkNodes();
}
}``````

### Implementation in Python

``````#Python program to count the number of sink nodes 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

#Connect the two node with  edge
def Connect(Self,Start,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

#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.PrintGraph();
g.SinkNodes();

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

## 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.

### 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!

Live masterclass