数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚学
法学生成指定固定度序列的图的 C++ 程序
这个 C++ 程序表示针对给定的度序列生成一个无向图。此算法的时间复杂度为 O(v*v)，并且不包括自边和多重边。
算法
Begin To create the graph, Create the first loop to connect each vertex ‘i’. Create second nested loop to connect the vertex ‘i’ to 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 using PrintMatrix(). End
示例代码
#include<iostream>
#include<iomanip>
using namespace std;
void PrintMatrix(int matrix[][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";
for(i = 0; i < n; i++) {
cout<<setw(4)<<"("<<i+1<<")";
for(j = 0; j < n; j++) {
cout<<setw(5)<<matrix[i][j];
}
cout<<"\n\n";
}
}
int main() {
int N, i, j, AdjMat[20][20] = {0};
cout<<"Enter the number of vertex in the graph: ";
cin>>N;
int degseq[N];
for(i = 0; i < N; i++) {
cout<<"Enter the degree of "<<i+1<<" vertex: ";
cin>>degseq[i];
}
for(i = 0; i < N; i++) {
for(j = i+1; j < N; j++) {
(degseq[i] > 0 && degseq[j] > 0) {
degseq[i]--;
degseq[j]--;
AdjMat[i][j] = 1;
AdjMat[j][i] = 1;
}
}
}
PrintMatrix(AdjMat, N);
}输出
Enter the number of vertexes of the graph: 5 Enter the number of edges of the graph: 4 Enter the vertex pair for edge 1 V(1): 2 V(2): 1 Enter the vertex pair for edge 2 V(1): 3 V(2): 2 Enter the vertex pair for edge 3 V(1): 1 V(2): 1 Enter the vertex pair for edge 4 V(1): 3 V(2): 1 (1) (2) (3) (4) (5) (1) 0 1 1 1 1 (2) 1 0 0 1 0 (3) 1 0 0 0 0 (4) 1 1 0 0 1 (5) 1 0 0 1 0
更新于:2019-07-30
222 次浏览
广告