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 in-degree and out-degree 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 in-degree and out-degree of each vertex. In-degree of a vertex is the count of edges that are coming into the vertex, while out-degree is the count of edges going out from the vertex. The article aims to explain this concept and provide a step-by-step 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 in-degree and out-degree of each vertex are as follows:

• Vertex 0: In-degree: 2, Out-degree: 3
• Vertex 1: In-degree: 3, Out-degree: 0
• Vertex 2: In-degree: 2, Out-degree: 1
• Vertex 3: In-degree: 1, Out-degree: 1
• Vertex 4: In-degree: 0, Out-degree: 2
• Vertex 5: In-degree: 1, Out-degree: 2

Idea to Solve the Problem

To calculate the in-degree and out-degree 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 in-degrees and the other for out-degrees. For each vertex, we iterate through its adjacency list to update the counts.

Pseudocode

Here's the pseudocode for calculating and displaying the in-degree and out-degree of each vertex:

procedure findDegrees(graph):
    initialize in-degree and out-degree arrays
    
    for each vertex in graph:
        iterate through its adjacency list
            update in-degree and out-degree arrays
    
    for each vertex in graph:
        print vertex, in-degree[vertex], and out-degree[vertex]

Algorithm Explanation

1. Initialize arrays to store in-degree and out-degree counts for each vertex.
2. Iterate through each vertex in the graph.
3. For each vertex, traverse its adjacency list: a. Update the in-degree and out-degree arrays for each adjacent vertex.
4. Iterate through the graph again to print the vertex along with its in-degree and out-degree.

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.