Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction📙
2.
Terms to Remember👩‍💻
3.
Problem Statement🕵️‍♀️
4.
Example 📖 
5.
Approach✍️
6.
Solutions📚
7.
Frequently Asked Questions
7.1.
What is a graph?
7.2.
What is the Degree of the node?
7.3.
What is an adjacency matrix?
7.4.
What is an undirected graph?
8.
Conclusion
Last Updated: Mar 27, 2024
Easy

Construct a graph from the given degrees of all vertices

Author yuvatimankar
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction📙

Graph data structure is among the most important and amazing topics to learn in computer science as they are used in various fields such as Google Maps, Circuit Design, etc. 

Constructing a graph from the given degrees of all vertices

So, in this article, we will write code for constructing a  graph from the given degrees of all vertices.

To know the logic behind the code, stay till the end!

Read also: Application of graph data structure

Terms to Remember👩‍💻

📝 Graph: A graph is a mathematical representation of a network describing the relationship between points and lines.

📝 Degree of a node: It is the number of edges incident to that node. The Degree of vertex v is denoted by deg(v).

Let’s see the degree of every node:

Node Degree
deg(a) 2
deg(b) 2
deg(c) 2
deg(d) 1
deg(e) 1
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Problem Statement🕵️‍♀️

We need to construct a graph for a given degree of all vertices. This algorithm creates an undirected graph for the given degree sequence. The graph given here does not include multiple edges and self-edge.

Example 📖 

Input: deg[ ] = { 2, 2, 1, 2, 1 }

Output : 

            (0)  (1)  (2)  (3)  (4)

     (0)    0    1    1     0    0

     (1)    1    0    0     1    0

     (2)    1    0    0     0    0

     (3)    0    1    0     0    1

     (4)    0    0    0     1    0

Explanation: The input we are given consists of 4 vertices with the Degree of vertex one as 2, degree of vertex two as 2, Degree of vertex three as 1, Degree of vertex four as 2, and Degree of vertex five as 1. Given below is the graph that follows the given condition:

Approach✍️

🎯 First, we need to take the input, the number of vertices, and their corresponding Degree.

🎯 Then, we need to declare the adjacency matrix[ ][ ] to contain the graph.

🎯 For creating the graph, we will make the first loop to connect each vertex ‘i’.

🎯 In the next step, we will create a second nested loop to connect the vertex ‘i’ to every valid vertex ‘j.’

🎯 If the Degree of vertex ‘j’ and ‘i’ is greater than zero, then we will connect them.

🎯 At last, we will print the adjacency matrix.

Solutions📚

🧿C++

#include <bits/stdc++.h>
using namespace std;
 
/* function for printing adjacency matrix */
void printMatrix(int degsequence[], int n)
{
    /* number of vertices = n */
    int matrix[n][n];
    memset(matrix, 0, sizeof(matrix));
 
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
 
            /* For each pair of vertex decrements */
            /* the Degree of both vertex.*/
            if (degsequence[i] > 0 && degsequence[j] > 0) {
                degsequence[i]--;
                degsequence[j]--;
                matrix[i][j] = 1;
                matrix[j][i] = 1;
            }
        }
    }
 
    /* Printing the result */
    cout << "\n"
         << setw(3) << "     ";
    for (int i = 0; i < n; i++)
        cout << setw(3) << "(" << i << ")";
    cout << "\n\n";
    for (int i = 0; i < n; i++) {
        cout << setw(4) << "(" << i << ")";
        for (int j = 0; j < n; j++)
            cout << setw(5) << matrix[i][j];
        cout << "\n";
    }
}
 
/* main function */
int main()
{
    int degsequence[] = { 2,2,1,2 };
    int n = sizeof(degsequence) / sizeof(degsequence[0]);
    printMatrix(degsequence, n);
    return 0;
}


Output:

           (0)   (1)   (2)   (3)
    (0)     0     1     1     0
    (1)     1     0     0     1
    (2)     1     0     0     0
    (3)     0     1     0     0


Time complexity:  Complexity in a graph is marked as v. And in the above example, as we can see, we have used for loop inside for loop, so the time complexity of the above code is O(v*v).

Space complexity: The space complexity for finding the adjacency matrix is O(v*v).

🧿 Java

import java.util.*;
 
class CN
{
 
/* A function to print the adjacency matrix. */
static void printMatrix(int degsequence[], int n)
{
    /* n is the number of vertices */
    int [][]matrix = new int[n][n];
 
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
 
            /* For each pair of vertex decrements */
            /* the Degree of both vertex. */
            if (degsequence[i] > 0 && degsequence[j] > 0)
            {
                degsequence[i]--;
                degsequence[j]--;
                matrix[i][j] = 1;
                matrix[j][i] = 1;
            }
        }
    }
 
    /* Print the result in the specified format */
    System.out.print("\n" + setw(3) + "     ");
     
    for (int i = 0; i < n; i++)
        System.out.print(setw(3) + "(" + i + ")");
    System.out.print("\n\n");
    for (int i = 0; i < n; i++)
    {
        System.out.print(setw(4) + "(" + i + ")");
         
        for (int j = 0; j < n; j++)
            System.out.print(setw(5) + matrix[i][j]);
        System.out.print("\n");
    }
}
 
static String setw(int n)
{
    String space = "";
    while(n-- > 0)
        space += " ";
    return space;
}
 
/* Driver Code */
public static void main(String[] args)
{
    int degsequence[] = { 2, 2, 1, 2 };
    int n = degsequence.length;
    printMatrix(degsequence, n);
}
}


Output:

            (0)  (1)  (2)   (3)
    (0)     0     1     1     0
    (1)     1     0     0     1
    (2)     1     0     0     0
    (3)     0     1     0     0


Time complexity Complexity in a graph is marked as v. And in the above example, as we can see, we have used for loop inside for loop, so the time complexity of the above code is O(v*v).

Space complexity: The space complexity for finding the adjacency matrix is O(v*v).

🧿 Python

def printMatrix(degsequence, n):
     
    # n is the number of vertices
    matrix = [[0] * n for i in range(n)]
 
    for i in range(n):
        for j in range(i + 1, n):
 
            # For each pair of vertex decrement
            # the Degree of both vertex.
            if (degsequence[i] > 0 and degsequence[j] > 0):
                degsequence[i] -= 1
                degsequence[j] -= 1
                matrix[i][j] = 1
                matrix[j][i] = 1
 
    # Print the result in the specified form
    print("      ", end = " ")
    for i in range(n):
        print(" ", "(", i, ")", end = "")
    print()
    print()
    for i in range(n):
        print(" ", "(", i, ")", end = "")
        for j in range(n):
            print("     ", matrix[i][j], end = "")
        print()
 
# Driver Code
if __name__ == '__main__':
    degsequence = [2, 3 , 2 , 2]
    n = len(degsequence)
    printMatrix(degsequence, n)
 


Output:

           ( 0 )  ( 1 )  ( 2 )  ( 3 )
  ( 0 )      0      1      1      0
  ( 1 )      1      0      1      1
  ( 2 )      1      1      0      0
  ( 3 )      0      1      0      0


Time complexity Complexity in a graph is marked as v. And in the above example, as we can see, we have used for loop inside for loop, so the time complexity of the above code is O(v*v).

Space complexity: The space complexity for finding the adjacency matrix is O(v*v).

🧿 C#

/* C# program to generate a graph for a
 given fixed degrees */
using System;
     
class CN
{
 
/* A function to print the adjacency matrix. */
static void printMatrix(int []degsequence, int n)
{
    /* n is the number of vertices */
    int [,]matrix = new int[n, n];
 
    for (int i = 0; i < n; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
 
            /* For each pair of vertex decrements 
             the Degree of both vertex. */
            if (degsequence[i] > 0 && degsequence[j] > 0)
            {
                degsequence[i]--;
                degsequence[j]--;
                matrix[i, j] = 1;
                matrix[j, i] = 1;
            }
        }
    }
 
    /* Print the result in the specified format */
    Console.Write("\n" + setw(3) + "     ");
     
    for (int i = 0; i < n; i++)
        Console.Write(setw(3) + "(" + i + ")");
    Console.Write("\n\n");
    for (int i = 0; i < n; i++)
    {
        Console.Write(setw(4) + "(" + i + ")");
         
        for (int j = 0; j < n; j++)
            Console.Write(setw(5) + matrix[i, j]);
        Console.Write("\n");
    }
}
 
static String setw(int n)
{
    String space = "";
    while(n-- > 0)
        space += " ";
    return space;
}
 
/* Driver Code */
public static void Main(String[] args)
{
    int []degsequence = { 2, 2, 1,2 };
    int n = degsequence.Length;
    printMatrix(degsequence, n);
}
}


Output:

            (0)   (1)   (2)   (3)
    (0)     0     1      1     0
    (1)     1     0      0     1
    (2)     1     0      0     0
    (3)     0     1      0     0


Time complexity Complexity in a graph is marked as v. And in the above example, as we can see, we have used for loop inside for loop, so the time complexity of the above code is O(v*v).

Space complexity: The space complexity for finding the adjacency matrix is O(v*v).
Check out this problem - No of Spanning Trees in a Graph

Frequently Asked Questions

What is a graph?

The graph is a mathematical representation of a network, and it describes the relationship between points and lines.

What is the Degree of the node?

The Degree of a node is the number of edges incident to that node.

What is an adjacency matrix?

An adjacency matrix is a square matrix utilized to describe a finite graph. It is also known as a connection matrix.

What is an undirected graph?

Undirected graphs are the graphs that have edges that do not have a direction.

Conclusion

In this article, we have discussed how to construct a graph from given degrees of all vertices with the help of some examples. We started with the introduction, and then we saw terms to remember, problem statement, approach, and solutions.

Recommended Readings:

Refer to our Guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. Enroll in our courses and refer to the mock test and problems available. Take a look at the interview experiences and interview bundle for placement preparations.

Happy Learning Ninja! 🥷

Live masterclass