# Construct a graph from given degrees of all vertices

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)
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach :
1- Take the input of the number of vertexes and their corresponding degree.
2- Declare adjacency matrix, mat[ ][ ] to store the graph.
3- To create the graph, create the first loop to connect each vertex ‘i’.
4- Second nested loop to connect the vertex ‘i’ to the every valid vertex ‘j’, next to it.
5- If the degree of vertex ‘i’ and ‘j’ are more than zero then connect them.
6- Print the adjacency matrix.

Based on the above explanation, below are implementations:

## C++

 `// C++ program to generate a graph for a ` `// given fixed degrees ` `#include ` `using` `namespace` `std; ` ` `  `// A function to print the adjacency matrix. ` `void` `printMat(``int` `degseq[], ``int` `n) ` `{ ` `    ``// n is number of vertices ` `    ``int` `mat[n][n]; ` `    ``memset``(mat, 0, ``sizeof``(mat)); ` ` `  `    ``for` `(``int` `i = 0; i < n; i++) { ` `        ``for` `(``int` `j = i + 1; j < n; j++) { ` ` `  `            ``// For each pair of vertex decrement ` `            ``// the degree of both vertex. ` `            ``if` `(degseq[i] > 0 && degseq[j] > 0) { ` `                ``degseq[i]--; ` `                ``degseq[j]--; ` `                ``mat[i][j] = 1; ` `                ``mat[j][i] = 1; ` `            ``} ` `        ``} ` `    ``} ` ` `  `    ``// Print the result in specified format ` `    ``cout << ````" "``` `         ``<< setw(3) << ``"     "``; ` `    ``for` `(``int` `i = 0; i < n; i++) ` `        ``cout << setw(3) << ``"("` `<< i << ``")"``; ` `    ``cout << ````" "````; ` `    ``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 << ````" "````; ` `    ``} ` `} ` ` `  `// driver program to test above function ` `int` `main() ` `{ ` `    ``int` `degseq[] = { 2, 2, 1, 1, 1 }; ` `    ``int` `n = ``sizeof``(degseq) / ``sizeof``(degseq); ` `    ``printMat(degseq, n); ` `    ``return` `0; ` `} `

## Python3

# Python3 program to generate a graph
# for a given fixed degrees

# A function to prthe adjacency matrix.
def printMat(degseq, n):

# n is number of vertices
mat = [ * 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 (degseq[i] > 0 and degseq[j] > 0):
degseq[i] -= 1
degseq[j] -= 1
mat[i][j] = 1
mat[j][i] = 1

# Prthe result in 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(” “, mat[i][j], end = “”)
print()

# Driver Code
if __name__ == ‘__main__’:
degseq = [2, 2, 1, 1, 1]
n = len(degseq)
printMat(degseq, n)

# This code is contributed by PranchalK

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).

This article is attributed to GeeksforGeeks.org

Graph Graph

code

load comments