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.
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.
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
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
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
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
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
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.
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.
Find more such exciting algorithms in our library section, and solve interesting questions on our practice platform Coding Ninjas Studio. Keep Learning.