C ++程序通过随机边缘选择方法构造随机图
在此程序中，将为随机顶点和边缘生成随机图。该程序的时间复杂度为O（v*e）。其中v是顶点数，e是边数。
算法
Begin
Develop a function GenRandomGraphs(), with ‘e’ as the
number of edges and ‘v’ as the number of vertexes, in the argument list.
Assign random values to the number of vertex and edges of the graph, Using rand() function.
不论方向如何，都打印每个顶点的连接。
为没有度数的顶点打印“隔离的顶点”。
End示例
#include<iostream>
#include<stdlib.h>
using namespace std;
void GenRandomGraphs(int NOEdge, int NOVertex) {
int i, j, edge[NOEdge][2], count;
i = 0;
//Assign random values to the number of vertex and edges of the graph, Using rand().
while(i < NOEdge) {
edge[i][0] = rand()%NOVertex+1;
edge[i][1] = rand()%NOVertex+1;
//不论方向如何，都打印每个顶点的连接。
if(edge[i][0] == edge[i][1])
continue;
else {
for(j = 0; j < i; j++) {
if((edge[i][0] == edge[j][0] && edge[i][1] == edge[j][1]) || (edge[i][0] == edge[j][1] && edge[i][1] == edge[j][0]))i--;
}
}
i++;
}
cout<<"\nThe generated random graph is: ";
for(i = 0; i < NOVertex; i++) {
count = 0;
cout<<"\n\t"<<i+1<<"-> { ";
for(j = 0; j < NOEdge; j++) {
if(edge[j][0] == i+1) {
cout<<edge[j][1]<<" ";
count++;
} else if(edge[j][1] == i+1) {
cout<<edge[j][0]<<" ";
count++;
} else if(j== NOEdge-1&& count == 0)cout<<"孤立的顶点！";
//为没有度数的顶点打印“隔离的顶点”。
}
cout<<" }";
}
}
int main() {
int i, e, n;
cout<<"Random graph generation: ";
n= 7 + rand()%6;
cout<<"\nThe graph has "<<n<<" vertices";
e = rand()%((n*(n-1))/2);
cout<<"\nand has "<<e<<" edges.";
GenRandomGraphs(e, n);
}输出结果
Random graph generation:
The graph has 8 vertices
and has 18 edges.
The generated random graph is:
1-> { 5 4 2 }
2-> { 4 8 6 3 1 5 }
3-> { 5 4 7 2 }
4-> { 2 3 7 1 8 5 }
5-> { 3 1 7 4 2 8 }
6-> { 2 8 7 }
7-> { 4 3 5 6 }
8-> { 2 6 4 5 }热门推荐
10 新年门口花束祝福语简短
11 盘锦结婚祝福语大全简短
12 父母生日祝福语 简短独特
13 家庭恩爱祝福语简短英文
14 高考俄语祝福语大全简短
15 虎年祝福语 诗句唯美简短
16 生日婚礼祝福语简短精辟
17 虎年喝酒拜年祝福语简短
18 教师闺蜜祝福语简短