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 :
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 <bits/stdc++.h> 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[0]); 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 = [[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 (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).
leave a comment
1 Comments