Indegree of a vertex is defined as the number of incoming edges incident on a vertex in a directed graph.
Significance Of Indegree:
- Indegree of nodes in a tree is equal to 1 in most of the cases if it becomes more than one then the data structure changes to graph.
- If the Indegree of a node is equal to zero, then the node/vertex does not have any parent vertex and it is either the root of the graph or an isolated vertex.
How to calculate Indegree of a node?
Example of directed graph
Consider the above directed graph for calculation of indegree of a node or vertex.
For calculating the indegree, we calculate the number of arrows pointing towards the node. For e.g. for vertex V4 there are two arrows pointing toward the node with edges as e3 and e4. therefore Indegree(V4) =2
Similarly,
- Indegree(V5) =1 as there is only one arrow with edge e5.
- Indegree(V1) =1 as there is only one arrow with edge e6.
- Indegree(V2) =2 as there are two arrows with edges e1 and e7.
- Indegree(V3) =1 as there is only one arrow with edge e2.
This is how we calculate the indegree of a node in a directed graph.
Finding Indegre of Directed Graph using its adjacency list:
Approach:
- Make a array of size N name as indgree where indgree[i] denotes the no. of node that are pointing towards the ith Node
- For ith Node there would be list which will get by adjaceny.get(i). For this list element do indgree[element]++ for all elements
Below is implementation of Above:
C++
// C++ program for the above approach#include <iostream>#include <vector>using namespace std;void findInDegree(const vector<vector<int>>& adjList, int n){ vector<int> inDegree(n, 0); for (const vector<int>& list : adjList) { for (int element : list) { // Every vertex that has an incoming // edge from i inDegree[element]++; } } for (int k = 0; k < n; k++) { cout << "Vertex " << k << " has in-degree: " << inDegree[k] << endl; }}int main(){ // Adjacency list representation of the graph vector<vector<int>> adjacency = { // Vertices 3 and 4 have an incoming edge // from vertex 0 {3, 4}, // Vertex 3 and 2 has an incoming edge from vertex 1 {3, 2}, // no incoming edge from vertex 2 {}, // Vertices 2 and 4 have an incoming edge // from vertex 3 {2, 4}, // Vertices 2 and 3 have an incoming edge // from vertex 4 {2, 3}, // Vertices 1,4 and 6 have an incoming edge // from vertex 5 {1, 4, 6}, // Vertex 5 has an incoming edge from vertex 6 {5} }; int n = adjacency.size(); findInDegree(adjacency, n); return 0;}// This code is contributed by Pushpesh Raj. |
Java
import java.util.*;class GFG { static void findInDegree(List<List<Integer> > adjList, int n) { int indgree[] = new int[n]; for (List<Integer> list : adjList) { for (int element : list) // Every vertex that has an incoming // edge from i indgree[element]++; } for (int k = 0; k < n; k++) { System.out.println("Vertex " + k + " has indgree" + "\t" + indgree[k]); } } // Driver code public static void main(String args[]) { // Adjacency list representation of the graph List<List<Integer> > adjacency = new ArrayList<>(); // Vertices 3 and 4 have an incoming edge // from vertex 0 List<Integer> tmp = new ArrayList<Integer>(Arrays.asList(3, 4)); adjacency.add(tmp); // Vertex 3 and 2 has an incoming edge from vertex 1 tmp = new ArrayList<Integer>(Arrays.asList(3, 2)); adjacency.add(tmp); // no incoming edge from vertex 2 tmp = new ArrayList<Integer>(Arrays.asList()); adjacency.add(tmp); // Vertices 2 and 4 have an incoming edge // from vertex 3 tmp = new ArrayList<Integer>(Arrays.asList(2, 4)); adjacency.add(tmp); // Vertices 2 and 3 have an incoming edge // from vertex 4 tmp = new ArrayList<Integer>(Arrays.asList(2, 3)); adjacency.add(tmp); // Vertices 1,4 and 6 have an incoming edge // from vertex 5 tmp = new ArrayList<Integer>( Arrays.asList(1, 4, 6)); adjacency.add(tmp); // Vertex 5 has an incoming edge from vertex 6 tmp = new ArrayList<Integer>(Arrays.asList(5)); adjacency.add(tmp); int n = adjacency.size(); findInDegree(adjacency, n); // This Code is Contributed By Vikas Bishnoi }} |
Python3
def find_in_degree(adj_list, n): in_degree = [0] * n for adj_vertices in adj_list: for vertex in adj_vertices: # Every vertex that has an incoming edge from vertex i in_degree[vertex] += 1 for k in range(n): print(f"Vertex {k} has in-degree: {in_degree[k]}")if __name__ == "__main__": # Adjacency list representation of the graph adjacency = [ [3, 4], # Vertices 3 and 4 have an incoming edge from vertex 0 [3, 2], # Vertex 3 and 2 has an incoming edge from vertex 1 [], # no incoming edge from vertex 2 [2, 4], # Vertices 2 and 4 have an incoming edge from vertex 3 [2, 3], # Vertices 2 and 3 have an incoming edge from vertex 4 [1, 4, 6], # Vertices 1, 4, and 6 have an incoming edge from vertex 5 [5] # Vertex 5 has an incoming edge from vertex 6 ] n = len(adjacency) find_in_degree(adjacency, n) |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{ static void findindgree(List<List<int>> adjList, int n) { int[] indgree = new int[n]; foreach (List<int> list in adjList) { foreach (int element in list) { // Every vertex that has an incoming // edge from i indgree[element]++; } } for (int k = 0; k < n; k++) { Console.WriteLine("Vertex " + k + " has indgree" + "\t" + indgree[k]); } } // Driver code public static void Main(string[] args) { // Adjacency list representation of the graph List<List<int>> adjacency = new List<List<int>>(); // Vertices 3 and 4 have an incoming edge from vertex 0 List<int> tmp = new List<int>(new int[] { 3, 4 }); adjacency.Add(tmp); // Vertex 3 and 2 have an incoming edge from vertex 1 tmp = new List<int>(new int[] { 3, 2 }); adjacency.Add(tmp); // No incoming edge from vertex 2 tmp = new List<int>(); adjacency.Add(tmp); // Vertices 2 and 4 have an incoming edge from vertex 3 tmp = new List<int>(new int[] { 2, 4 }); adjacency.Add(tmp); // Vertices 2 and 3 have an incoming edge from vertex 4 tmp = new List<int>(new int[] { 2, 3 }); adjacency.Add(tmp); // Vertices 1, 4, and 6 have an incoming edge from vertex 5 tmp = new List<int>(new int[] { 1, 4, 6 }); adjacency.Add(tmp); // Vertex 5 has an incoming edge from vertex 6 tmp = new List<int>(new int[] { 5 }); adjacency.Add(tmp); int n = adjacency.Count; findindgree(adjacency, n); }}// This code is contributed by Utkarsh Kumar |
Javascript
// JavaScript program for finding in-degrees of vertices in a directed graphfunction findInDegree(adjList, n) { let inDegree = Array(n).fill(0); for (let list of adjList) { for (let element of list) { // Every vertex that has an incoming edge from i inDegree[element]++; } } for (let k = 0; k < n; k++) { console.log(`Vertex ${k} has in-degree: ${inDegree[k]}`); }}// Main functionfunction main() { // Adjacency list representation of the graph let adjacency = [ // Vertices 3 and 4 have an incoming edge from vertex 0 [3, 4], // Vertex 3 and 2 have an incoming edge from vertex 1 [3, 2], // no incoming edge from vertex 2 [], // Vertices 2 and 4 have an incoming edge from vertex 3 [2, 4], // Vertices 2 and 3 have an incoming edge from vertex 4 [2, 3], // Vertices 1, 4, and 6 have an incoming edge from vertex 5 [1, 4, 6], // Vertex 5 has an incoming edge from vertex 6 [5] ]; let n = adjacency.length; findInDegree(adjacency, n);}// Calling the main functionmain(); |
Output
Vertex 0 has indgree 0 Vertex 1 has indgree 1 Vertex 2 has indgree 3 Vertex 3 has indgree 3 Vertex 4 has indgree 3 Vertex 5 has indgree 1 Vertex 6 has indgree 1
Time Complexity: O(V + E) where V and E are the numbers of vertices and edges in the graph respectively.
Auxiliary Space: O(V) As additionally we only use indegree array to store output
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
