Construct a graph from given degrees of all vertices
Last Updated :
31 Jan, 2023
This is a C++ program to generate a graph for a given fixed degree sequence. This algorithm generates a undirected graph for the given degree sequence.It does not include self-edge and multiple edges.
Examples:
Input : degrees[] = {2, 2, 1, 1}
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
Explanation : We are given that there
are four vertices with degree of vertex
0 as 2, degree of vertex 1 as 2, degree
of vertex 2 as 1 and degree of vertex 3
as 1. Following is graph that follows
given conditions.
(0)----------(1)
| |
| |
| |
(2) (3)
Approach :
- Take the input of the number of vertexes and their corresponding degree.
- Declare adjacency matrix, mat[ ][ ] to store the graph.
- To create the graph, create the first loop to connect each vertex ‘i’.
- Second nested loop to connect the vertex ‘i’ to the every valid vertex ‘j’, next to it.
- If the degree of vertex ‘i’ and ‘j’ are more than zero then connect them.
- Print the adjacency matrix.
Based on the above explanation, below are implementations:
C++
#include <bits/stdc++.h>
using namespace std;
void printMat(int degseq[], int n)
{
int mat[n][n];
memset(mat, 0, sizeof(mat));
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (degseq[i] > 0 && degseq[j] > 0) {
degseq[i]--;
degseq[j]--;
mat[i][j] = 1;
mat[j][i] = 1;
}
}
}
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) << mat[i][j];
cout << "\n";
}
}
int main()
{
int degseq[] = { 2, 2, 1, 1, 1 };
int n = sizeof(degseq) / sizeof(degseq[0]);
printMat(degseq, n);
return 0;
}
|
Java
import java.util.*;
class GFG
{
static void printMat(int degseq[], int n)
{
int [][]mat = new int[n][n];
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (degseq[i] > 0 && degseq[j] > 0)
{
degseq[i]--;
degseq[j]--;
mat[i][j] = 1;
mat[j][i] = 1;
}
}
}
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) + mat[i][j]);
System.out.print("\n");
}
}
static String setw(int n)
{
String space = "";
while(n-- > 0)
space += " ";
return space;
}
public static void main(String[] args)
{
int degseq[] = { 2, 2, 1, 1, 1 };
int n = degseq.length;
printMat(degseq, n);
}
}
|
Python3
def printMat(degseq, n):
mat = [[0] * n for i in range(n)]
for i in range(n):
for j in range(i + 1, n):
if (degseq[i] > 0 and degseq[j] > 0):
degseq[i] -= 1
degseq[j] -= 1
mat[i][j] = 1
mat[j][i] = 1
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(" ", mat[i][j], end = "")
print()
if __name__ == '__main__':
degseq = [2, 2, 1, 1, 1]
n = len(degseq)
printMat(degseq, n)
|
C#
using System;
class GFG
{
static void printMat(int []degseq, int n)
{
int [,]mat = new int[n, n];
for (int i = 0; i < n; i++)
{
for (int j = i + 1; j < n; j++)
{
if (degseq[i] > 0 && degseq[j] > 0)
{
degseq[i]--;
degseq[j]--;
mat[i, j] = 1;
mat[j, i] = 1;
}
}
}
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) + mat[i, j]);
Console.Write("\n");
}
}
static String setw(int n)
{
String space = "";
while(n-- > 0)
space += " ";
return space;
}
public static void Main(String[] args)
{
int []degseq = { 2, 2, 1, 1, 1 };
int n = degseq.Length;
printMat(degseq, n);
}
}
|
Javascript
<script>
function printMat(degseq,n)
{
let mat = new Array(n);
for(let i=0;i<n;i++)
{
mat[i]=new Array(n);
for(let j=0;j<n;j++)
mat[i][j]=0;
}
for (let i = 0; i < n; i++)
{
for (let j = i + 1; j < n; j++)
{
if (degseq[i] > 0 && degseq[j] > 0)
{
degseq[i]--;
degseq[j]--;
mat[i][j] = 1;
mat[j][i] = 1;
}
}
}
document.write("<br>" + setw(3) + " ");
for (let i = 0; i < n; i++)
document.write(setw(3) + "(" + i + ")");
document.write("<br><br>");
for (let i = 0; i < n; i++)
{
document.write(setw(4) + "(" + i + ")");
for (let j = 0; j < n; j++)
document.write(setw(5) + mat[i][j]);
document.write("<br>");
}
}
function setw(n)
{
let space = "";
while(n-- > 0)
space += " ";
return space;
}
let degseq=[2, 2, 1, 1, 1];
let n = degseq.length;
printMat(degseq, n);
</script>
|
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 0
(4) 0 0 0 0 0
Time Complexity: O(v*v).
Space complexity : O(n^2) because it creates a 2-dimensional array (matrix) of size n * n, where n is the number of vertices in the graph.
Please Login to comment...