Show degree of vertex in directed graph
In a directed graph, the degree of a vertex is the count of edges that are incident to the vertex. This concept helps us understand how connected a vertex is to the rest of the graph. This article focuses on demonstrating how to calculate and display the indegree and outdegree of each vertex in a directed graph through code.
Problem Statement and Description
Given a directed graph represented using an adjacency list, the task is to find the indegree and outdegree of each vertex. Indegree of a vertex is the count of edges that are coming into the vertex, while outdegree is the count of edges going out from the vertex. The article aims to explain this concept and provide a stepbystep code implementation to calculate and display the degrees of vertices in the graph.
Example
Consider the directed graph:
0 > 1, 2, 5
1 >
2 > 3
3 > 1
4 > 0, 1
5 > 0, 2
In this graph, the indegree and outdegree of each vertex are as follows:
 Vertex 0: Indegree: 2, Outdegree: 3
 Vertex 1: Indegree: 3, Outdegree: 0
 Vertex 2: Indegree: 2, Outdegree: 1
 Vertex 3: Indegree: 1, Outdegree: 1
 Vertex 4: Indegree: 0, Outdegree: 2
 Vertex 5: Indegree: 1, Outdegree: 2
Idea to Solve the Problem
To calculate the indegree and outdegree of each vertex, we need to traverse the adjacency list and count the number of edges incident to each vertex. We can achieve this by keeping two arrays: one for indegrees and the other for outdegrees. For each vertex, we iterate through its adjacency list to update the counts.
Pseudocode
Here's the pseudocode for calculating and displaying the indegree and outdegree of each vertex:
procedure findDegrees(graph):
initialize indegree and outdegree arrays
for each vertex in graph:
iterate through its adjacency list
update indegree and outdegree arrays
for each vertex in graph:
print vertex, indegree[vertex], and outdegree[vertex]
Algorithm Explanation
 Initialize arrays to store indegree and outdegree counts for each vertex.
 Iterate through each vertex in the graph.
 For each vertex, traverse its adjacency list: a. Update the indegree and outdegree arrays for each adjacent vertex.
 Iterate through the graph again to print the vertex along with its indegree and outdegree.
Indegree : Number of incoming edges of a specified vertex.
Outdegree : Number of outgoing edges of a specified vertex.

1) Find indegree and outdegree of a directed graph in c
2) Find indegree and outdegree of a directed graph in c++
3) Find out indegree and outdegree of a directed graph in java
4) Find indegree and outdegree of a directed graph in golang
5) Find indegree and outdegree of a directed graph in c#
6) Find indegree and outdegree of a directed graph in vb.net
7) Find indegree and outdegree of a directed graph in php
8) Find indegree and outdegree of a directed graph in node js
9) Find indegree and outdegree of a directed graph in typescript
10) Find indegree and outdegree of a directed graph in python
11) Find indegree and outdegree of a directed graph in ruby
12) Find indegree and outdegree of a directed graph in scala
13) Find indegree and outdegree of a directed graph in swift
14) Find indegree and outdegree of a directed graph in kotlin
Time Complexity
The algorithm traverses the adjacency list twice. In the worst case, each edge is considered twice, leading to a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment