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;
}
You can also try this code with Online C++ Compiler
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);
}
}
You can also try this code with Online Java Compiler
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)
You can also try this code with Online Python Compiler
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! 🥷
84+ registered