Posted on by Kalkicode
Code Graph

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.

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.

Comment

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