C++ Programming Code Examples C++ > Sorting Searching Code Examples Check if any Graph is Possible to be Constructed for a Given Degree Sequence Check if any Graph is Possible to be Constructed for a Given Degree Sequence - This algorithm checks whether a undirected graph can be generated from a given degree sequence. - The graph should not have a self-edge and multiple edges. - The time complexity of this algorithm is O(v*v). - This algorithm takes the input of the number of vertexes and their corresponding degree. - It Checks various constraints and tries to build the graph. - If it fails, no valid graph can be created from the given sequence. - Exit. #include<iostream> #include<iomanip> using namespace std; // A function to print the adjacency matrix. void PrintMat(int mat[][20], int n) { int i, j; cout<<"\n\n"<<setw(3)<<" "; for(i = 0; i < n; i++) cout<<setw(3)<<"("<<i+1<<")"; cout<<"\n\n"; // Print 1 if the corresponding vertexes are connected otherwise 0. for(i = 0; i < n; i++) { cout<<setw(4)<<"("<<i+1<<")"; for(j = 0; j < n; j++) { cout<<setw(5)<<mat[i][j]; } cout<<"\n\n"; } } int main() { int NOV, i, j, AdjMat[20][20] = {0}; cout<<"Enter the number of vertex in the graph: "; cin>>NOV; int degseq[NOV]; // Take input of the degree sequence. for(i = 0; i < NOV; i++) { cout<<"Enter the degree of "<<i+1<<" vertex: "; cin>>degseq[i]; } for(i = 0; i < NOV; i++) { for(j = i+1; j < NOV; j++) { // For each pair of vertex decrement the degree of both vertex. if(degseq[i] > 0 && degseq[j] > 0) { degseq[i]--; degseq[j]--; AdjMat[i][j] = 1; AdjMat[j][i] = 1; } } } PrintMat(AdjMat, NOV); }